#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)。答案对 2312^{31} 取模。

输入格式

第一行为一个字符串,即算式。

接下来一行一个非负整数 m,表示限制条件的个数。

接下来 m 行每行 a,b,a 为某个大写字母,b 为某个数位,表示 a 这一字母不能等于 b。

输出格式

输出解的个数。由于这个值可能较大,对 2312^{31} 取模。

样例 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

数据范围与提示

对于所有数据,m≤10000。下述的算式长度即输入第一行字符串的长度。对于所有数据,m\le 10000。下述的算式长度即输入第一行字符串的长度。

Subtask1(20 pts):算式长度不超过5。Subtask 1(20\,\mathrm{pts}):算式长度不超过 5。

Subtask2(20 pts):算式长度不超过17。Subtask 2(20\,\mathrm{pts}):算式长度不超过 17。

Subtask3(20 pts):算式长度不超过20。Subtask 3(20\,\mathrm{pts}):算式长度不超过 20。

Subtask4(20 pts):算式长度不超过23。Subtask 4(20\,\mathrm{pts}):算式长度不超过 23。

Subtask5(20 pts):算式长度不超过26。Subtask 5(20\,\mathrm{pts}):算式长度不超过 26。