题目描述

给出一个整数$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$个整数（满足条件的个数）

样例

234 2
2 5
3 6

4