Description

Given an integer n (n ≤ 2000) and k transformation rules (k ≤ 15).
Rules:
① One digit can be transformed into another digit.
② The right-hand side digit in a rule cannot be zero.
For example: n = 234, k = 2, and the rules are
2 → 5
3 → 6
The integer 234 can be transformed into the following possible integers (including the original number): 234, 534, 264, 564, totaling 4 distinct numbers.
The task is to find out how many distinct integers can be generated after any number of transformations (0 or more). Only the count of distinct integers is required as output.

Input Format

n
k
x₁ y₁
x₂ y₂
…
xₖ yₖ

Output Format

The output should be a single integer (the count of distinct integers satisfying the condition).

234
2
2 5
3 6

4