题目描述

给出一个整数 ${n(n<10^{30})}$ 和 ${k}$ 个变换规则 ${(k \le 15)}$。

对于每个变化规则，有如下约束：

• $1$. 将一个数字可以变换为另一个数字；
• $2$. 规则的右部不能为${0}$。

例如：${n=234}$，有规则 ${k=2}$:

• ${2 \to 5}$
• ${3 \to 6}$

则 ${234}$ 经过变换后可能产生出的整数为（包括原数）有

${234}$、

${534}$、

${264}$、

${564}$，

共 ${4}$ 个不同的产生数。

给出一个整数 ${n}$ 和 ${k}$ 个规则。求经过任意次的变换（$0$次或多次），能产生出多少个不同的整数，请输出变化后的个数。

输入格式

第一行两个整数 ${n,k}$。 接下来 ${k}$ 行，每行两个整数 ${x_i,y_i}$。

输出格式

输出能生成的数字个数。

样例

输入样例

234 2
2 5
3 6

输出样例

4