题目描述

本题是杭州学军中学“图灵杯”网络邀请赛题目加强，注意有改动。

小学生 zzq 喜欢做小学数学题。一天，他在口算题卡上发现了这样一道题：有算式 $ABC+DBC=BCE$，求出任何一个解。zzq 想了想，求出了一个解 $124+124=248$（$A=1,B=2,C=4,D=1,E=8$）。zzq 又看了一眼题目，发现要求 $D\neq 1$，所以 zzq 只好又求出了一个解 $137+237=374$（$A=1,B=3,C=7,D=2,E=4$）。

zzq 觉得这类题目很有意思，因此希望你解决一些这样的问题。每个问题都形如「一个非空大写字母串 $+$ 一个非空大写字母串 $=$ 一个非空大写字母串」，其中每个大写字母代表一个数位，相同的大写字母代表相同的数位，不同的大写字母也可以代表相同的数位。此外，我们要求将字母替换为数位后等式成立，且被加数和结果均大于 $\mathbf 0$，且没有前导零。我们还可能有一些限制条件，限制条件形如某个大写字母不代表某个数位。

对于这样的一个问题，你需要求出可能的解的个数。解即实际的等式（如 $124+124=248$）。答案对 $2^{31}$ 取模。

输入格式

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

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

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

输出格式

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

A+B=C
2
B 2
C 5

26

PLOTS+ACTOR=FILMS
6
R 2
A 3
N 4
D 5
O 6
M 7

213880

数据范围与提示

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

Subtask $1$（$20\,\mathrm{pts}$）：算式长度不超过 $5$。

Subtask $2$（$20\,\mathrm{pts}$）：算式长度不超过 $17$。

Subtask $3$（$20\,\mathrm{pts}$）：算式长度不超过 $20$。

Subtask $4$（$20\,\mathrm{pts}$）：算式长度不超过 $23$。

Subtask $5$（$20\,\mathrm{pts}$）：算式长度不超过 $26$。

目前的数据很弱，欢迎 hack，如果没有管理员权限可以发帖。