9012 - 数的衍生
Time Limit : 1 秒
Memory Limit : 256 MB
一个正整数n(n<10^{30})按下面的规则可以衍生出另外的数字：
1、规定每1位数字可以变成另外的1位数字；
2、变换成的新数字不能是0；
3、新数字可以继续按规则变成另外的新数字
例如n=123，规则有2条，分别是2->5，3->6。按这个规则可以衍生出：126、153、156，和自身一共有4个数字。
现在给出k(1<=k<=15)条规则，请计算出本身加衍生的数字个数。
Input
第一行一个整数n和规则数量k
第二行开始共k行，每行一条规则，由两个用空格隔开的数字A和B，表示A可以变换为B
Output
一个数字，表示自身和衍生的数字的个数
Examples
Input
234 2 2 5 3 6
Output
4
Source
网络