3007 - 【XR-1】分块
时间限制 : 1 秒
内存限制 : 128 MB
有一个长度为 的序列,xht37 现在想分块维护它。
PinkRabbit 要求他只准将序列分成 种长度的块。
NaCly_Fish 要求他只准将序列分成 种长度的块。
同一个人可能会要求 xht37 多次相同的块长。
xht37 想同时满足 PinkRabbit 和 NaCly_Fish 要求,只好使用两个人都允许的长度分块。
xht37 想知道,有多少种不同的分块方案,答案对 取模。
输入
第一行一个正整数 ,表示序列的长度。
第二行一个正整数 ,表示 PinkRabbit 要求的分块长度的种类数。
第三行 个正整数,表示 PinkRabbit 要求的 种分块长度。
第四行一个正整数 ,表示 NaCly_Fish 要求的分块长度的种类数。
第五行 个正整数,表示 NaCly_Fish 要求的 种分块长度。
输出
输出一行一个整数,表示不同分块方案的种类数对 取模的值。
样例
输入复制
4 3 1 2 3 3 1 2 4
输出复制
5
输入复制
19260817 7 8 9 6 3 7 2 1 7 4 5 2 9 7 8 3
输出复制
859254329
提示
【样例 说明】
PinkRabbit 和 NaCly_Fish 都允许的块长为 。
长度为 的序列分块,每块长度为 的方案有:
共 种。
【数据规模与约定】
设最大块长为 。 对于 的数据,,。
来源
用户上传