题目描述

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

规则：

1. 1 个数字可以变换成另 1 个数字；
2. 规则中，右边的数字不能为零。

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

• $2 \to 5$
• $3 \to 6$

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

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

输入格式

第一行一个整数 $n$。

第二行一个整数 $k$。

接下来 $k$ 行，每行两个整数 $x_i, y_i$，表示一条变换规则。

输出格式

一个整数（满足条件的整数个数）。

样例

234
2
2 5
3 6

4

数据范围

• $n \le 2000$
• $k \le 15$