#993. 小学数学题
小学数学题
题目描述
小学生 zzq 喜欢做小学数学题。一天,他在口算题卡上发现了这样一道题:有算式 ABC+DBC=BCE,求出任何一个解。zzq 想了想,求出了一个解 124+124=248(A=1,B=2,C=4,D=1,E=8)。zzq 又看了一眼题目,发现要求 D≠1,所以 zzq 只好又求出了一个解 137+237=374(A=1,B=3,C=7,D=2,E=4)。
zzq 觉得这类题目很有意思,因此希望你解决一些这样的问题。每个问题都形如「一个非空大写字母串 + 一个非空大写字母串 = 一个非空大写字母串」,其中每个大写字母代表一个数位,相同的大写字母代表相同的数位,不同的大写字母也可以代表相同的数位。此外,我们要求将字母替换为数位后等式成立,且被加数和结果均大于 0,且没有前导零。我们还可能有一些限制条件,限制条件形如某个大写字母不代表某个数位。
对于这样的一个问题,你需要求出可能的解的个数。解即实际的等式(如 124+124=248)。答案对 取模。
输入格式
第一行为一个字符串,即算式。
接下来一行一个非负整数 m,表示限制条件的个数。
接下来 m 行每行 a,b,a 为某个大写字母,b 为某个数位,表示 a 这一字母不能等于 b。
输出格式
输出解的个数。由于这个值可能较大,对 取模。
样例 1
##输入
A+B=C
2
B 2
C 5
输出
26
样例 2 输入
PLOTS+ACTOR=FILMS
6
R 2
A 3
N 4
D 5
O 6
M 7
输出
213880
数据范围与提示