题目描述

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

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

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

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

$2$ → $5$

$3$ → $6$

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

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

输入格式

第一行输入一个整数 $n$； 第二行输入一个整数 $k$，随后 $k$ 行输入 $k$ 种规则。

输出格式

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

样例

样例输入 1

234
2
2 5
3 6

样例输出 1

4