题目描述

给出一个整数n（$n \lt 10^{30}$）和k个变换规则（k≤15）。

规则：

• 一位数可变换成另一个一位数。
• 规则的右部不能为零。

例如：n=234。有规则（k=2）：

• 2→5
• 3→6

上面的整数234经过变换后可能产生出的整数为（包括原数）:

• 234
• 534
• 264
• 564

共4种不同的产生数。

现在给出一个整数n和k个规则。求出经过任意次的变换（0次或多次），能产生出多少个不同整数。

仅要求输出个数。

输入格式

第一行两个整数n,k。

接下来k行，每行两个整数$x_i,y_i$。

输出格式

输出能生成的数字个数。

234 2
2 5
3 6

4