说明

　　问题描述

　　给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。

　　规则：

　　一位数可变换成另一个一位数：

　　规则的右部不能为零。

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

　　2－> 5

　　3－> 6

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

　　234

　　534

　　264

　　564

　　共 4 种不同的产生数

　　问题：

　　给出一个整数 n 和 k 个规则。

　　求出：

　　经过任意次的变换（0次或多次），能产生出多少个不同整数。

　　仅要求输出个数。
　　输入格式:
　　n k
　　x1 y1
　　x2 y2
　　... ...
　　xn yn
　　输出格式:
　　一个整数（满足条件的个数）：

输入格式

输入描述:

输入样例:
234 2
2 5
3 6

输出格式

输出描述:

输出样例:
4

样例

参考上文 

参考上文

提示

HINT:时间限制：1.0s 内存限制：256.0MB