题目描述

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

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

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

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

$2 → 5$

$3 → 6$

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

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

输入

n
k
x1 y1
x2 y2
....
xk yk

输出

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

234
2
2 5
3 6

4

提示

$n \leq 2000$

$k \leq 15$