Number Transformations

Problem Description

You are given an integer $n$ and $k$ transformation rules.

Rules:

• a one-digit number may be transformed into another one-digit number;
• the right-hand side of a rule may not be zero.

Example: $n=234$, $k=2$, with two rules:

• $2 \longrightarrow 5$
• $3 \longrightarrow 6$

The integer $234$ may be transformed into the following integers (including itself):

• $234$
• $534$
• $264$
• $564$

That is $4$ different numbers in total.

Given $n$ and $k$ rules, find how many different integers can be produced by applying the rules any number of times (zero or more). You only need to output the count.

Input Format

The first line contains two integers $n, k$, as described above.

The next $k$ lines each contain two integers $x_i, y_i$, describing one rule.

Output Format

One line: the number of different integers that can be produced.

Sample Input

234 2
2 5
3 6

Sample Output

4

Hint

For 100% of the data, $n < 10^{30}$ and $k \le 15$.

Source: NOIP 2002, Problem 3 of the Junior (Popular) group.