Ralph and arithmetic

Input

The first line contains an integer $n$ (1 \le n \le 10^{18}). The second line contains an integer $k$ (1 \le k \le 9) - the number of digits Ralph considers minor. The third line contains the minor digits d_1, \ldots, d_k (0 \le d_1 < d_2 < \ldots < d_k \le 9).

Output

Print one number - the number of numbers from $1$ to $n$ whose decimal notation does not contain minor digits.

Examples

Note

In the first test, all numbers from $1$ to $9$ are suitable, except for $3$ and $4$.

In the second test, only numbers $1$, $11$ and $111$ match.

In the third test, all numbers from $1$ to $5$ in length, consisting only of $3$ and $4$, are suitable.