说明

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

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

　　规则：

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

　　规则的右部不能为零。

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

　　2－> &nbsp 5

　　3－> &nbsp 6

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

　　234

　　534

　　264

　　564

　　共&nbsp 4&nbsp 种不同的产生数

　　问题：

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

　　求出：

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

　　仅要求输出个数。
　　输入格式:
　　n&nbsp k
　　x1&nbsp y1
　　x2&nbsp y2
　　...&nbsp ...
　　xn&nbsp yn
　　输出格式:
　　一个整数（满足条件的个数）：
样例输入
234&nbsp 2
2&nbsp 5
3&nbsp 6
样例输出
4