产生数

题目描述

给出一个整数$n(n<10^{30})$和$ k $个变换规则$(k \le 15)$。 规则: 一位数可变换成另一个一位数: 规则的右部不能为零。 例如:$n=234$。有规则($k=2$): $2$->$5$ $3$->$6$ 上面的整数$234$经过变换后可能产生出的整数为(包括原数): $234$ $534$ $264$ $564$ 共$4$ 种不同的产生数 问题: 给出一个整数 $n$ 和$ k$ 个规则。 求出: 经过任意次的变换($0$次或多次),能产生出多少个不同整数。 仅要求输出个数。

输入输出格式

输入格式


键盘输入,格式为: $n k$ $x_1 y_1$ $x_2 y_2$ ... ... $x_n y_n$

输出格式


屏幕输出,格式为: $1$个整数(满足条件的个数):

输入输出样例

输入样例 #1

234 2
2 5
3 6

输出样例 #1

4