产生数(Produce)

题目描述

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

规则：

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

例如：$n=234$，$k=2$，规则为 $2 \rightarrow 5$，$3 \rightarrow 6$。上面的整数 $234$ 经过变换后可能产生出的整数为（包括原数）$234, 534, 264, 564$ 共 $4$ 种不同的产生数。

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

输入

第一行一个整数 $n$；第二行一个整数 $k$。接下来 $k$ 行，每行两个整数 $x$ $y$，表示一个变换规则 $x \rightarrow y$（$y$ 不能为零）。

输出

输出一个整数，表示满足条件的整数个数。

样例输入

234
2
2 5
3 6

样例输出

4