暂无测试数据。

题目描述

给出一个整数 \(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
… …
xn yn


输出

输出一个整数为满足条件的整数个数。

样例输入

234
2
2 5
3 6

样例输出

4

数据范围限制

\(n \leq 2000\)
\(k \leq 15\)

来源

基础篇补充6.3