题目描述

给出一个整数 $n$ （ $n \le 2000$ ）和 $k$ 个变换规则（ $k \le 15$ ）。规则：

① $1$ 个数字可以变换成另 $1$ 个数字；

② 规则中，右边的数字不能为零。

例如： $n=234$ ， $k=2$ 规则为

$2 → 5$

$3 → 6$

上面的整数 $234$ 经过变换后可能产生出的整数为（包括原数） $234$ ， $534$ ， $264$ ， $564$ 共 $4$ 种不同的产生数。

求经过任意次的变换（ $0$ 次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。

输入格式

第一行两个整数 $n$ ， $k$ 。

接下来 $k$ 行，每行两个整数 $x_i$ ， $y_i$ 。

输出能生成的数字个数。