题目描述

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

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

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

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

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

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

$\red{234}$、

$\red{534}$、

$\red{264}$、

$\red{564}$，

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

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

输入格式

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

输出格式

输出能生成的数字个数。

样例

输入样例

234 2
2 5
3 6

输出样例

4