2171: 产生数

算法提高  产生数   
时间限制：1.0s     内存限制：256.0MB
     
　　问题描述

　　给出一个整数  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