[NOIP2002-普及] 产生数

题目描述

给出一个整数 $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：