#PQJ2470x15142. QOJ 2470_15142
QOJ 2470_15142
lxhgww 非常喜欢数字游戏,他发现,很多数都可以表示成两个相互反转的数之和,他把这个现象称为数的“镜像拆分”。比如 66 共有五种镜像拆分方法:
66=15+51
66=24+42
66=33+33
66=42+24
66=51+15
注意,前导 0 是不允许的,所以 66
60 + 06 不算做合法的镜像拆分。
现在 lxhgww 想知道,在 𝐾 进制下,对于在 [ 𝐴 , 𝐵 ] 区间内的数,其镜像拆分的方案数之和是多少?
输入格式
输入的第一行是一个数 𝐾 。
输入的第二行是一个数 𝑛 ,表示数字 𝐴 的长度。
接下来 𝑛 行,表示 𝐴 从低位开始的每一位数字。
然后是一个数 𝑚 ,表示数字 𝐵 的长度。
接下来 𝑚 行,表示 𝐵 从低位开始的每一位数字。
输出格式
输出一行,包含一个整数,表示镜像拆分的方案数之和。由于这个答案非常大,只需要输出这个答案除以 20110521 的余数。
样例数据 样例 1 输入 10 2 6 6 2 6 6 样例 1 输出 5 样例 2 输入 10 1 1 4 0 0 0 1 样例 2 输出 410 子任务
对于 20 % 的数据, 2 ≤ 𝐾 ≤ 100 , 1 ≤ 𝑛 , 𝑚 ≤ 100 。
对于 50 % 的数据, 2 ≤ 𝐾 ≤ 10 3 , 1 ≤ 𝑛 , 𝑚 ≤ 10 3 。
对于 100 % 的数据, 2 ≤ 𝐾 ≤ 10 5 , 1 ≤ 𝑛 , 𝑚 ≤ 10 5 。
对于所有的数据, 0 < 𝐴 ≤ 𝐵 ,且 𝐴 , 𝐵 的每一位数字都在 [ 0 , 𝐾 − 1 ] 的范围内,没有前导 0 。