题目描述

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

规则表示一位数字可以变换成另一位数字，规则右部不能为 0。每一位可以经过 0 次或多次变换。

例如 n=234,k=2，规则为 2 -> 5、3 -> 6，则 234 可以产生 234、534、264、564，共 4 个不同整数。

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

输入格式

第一行包含整数 n 和 k。

接下来 k 行，每行两个整数 x,y，表示数字 x 可以变换成数字 y。

输出格式

一行一个整数，表示能产生的不同整数个数。

样例输入 #1

234 2
2 5
3 6

样例输出 #1

4

数据范围与提示

n < 10^30，k <= 15。

可以把数字之间的变换看作有向图，先求每个数字能到达多少个数字，再用乘法原理计算答案。答案可能很大，需要使用高精度。

来源

洛谷 P1037 [NOIP2002 普及组] 产生数。