#2439. 「SCOI2011」镜像拆分

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

lxhgww 非常喜欢数字游戏,他发现,很多数都可以表示成两个相互反转的数之和,他把这个现象称为数的“镜像拆分”。比如 66 共有五种镜像拆分方法:

  • 66=15+51
  • 66=24+42
  • 66=33+33
  • 66=42+24
  • 66=51+15

注意,前导 0 是不允许的,所以 66=60+06 不算做合法的镜像拆分。
现在 lxhgww 想知道,在 K 进制下,对于在 [A,B] 区间内的数,其镜像拆分的方案数之和是多少?

输入格式

输入的第一行是一个数 K
输入的第二行是一个数 n ,表示数字 A 的长度。
接下来 n 行,表示 A 从低位开始的每一位数字。
然后是一个数 m ,表示数字 B 的长度。
接下来 m 行,表示 B 从低位开始的每一位数字。

输出格式

输出一行,包一个整数,表示镜像拆分的方案数之和。由于这个答案非常大,只需要输出这个答案除以 20110521 的余数。

样例

输入样例 1

10
2
6
6
2
6
6

输出样例 1

5

输入样例 2

10
1
1
4
0
0
0
1

输出样例 2

410

数据范围与提示

对于 20\% 的数据, 2 \le K \le 100 , 1 \le n , m \le 100
对于 50\% 的数据, 2 \le K \le 10^3 , 1 \le n , m \le 10^3
对于 100\% 的数据, 2 \le K \le 10^5 , 1 \le n , m \le 10^5 , 0<A \le B ,且 A B 的每一位数字都在 [0,K-1] 的范围内,没有前导 0