Password

Interview

Time limit1sMemory limit64 MB

Summary

Count n-digit strings over 0-9 that contain every one of the m given digits at least once.

Level: Medium5 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

Ungchan is a stubborn thief. When he cracks a safe he tries every combination without skipping any. If he knows the password is 3 characters long, he presses 000, 001, 002, 003, ..., 998, 999 in order.

Ungchan also has foresight, so he learns some of the digits that appear in the password. Once he knows that a 3-character password contains a 0, a number like 999 with no 0 in it drops out. Numbers such as 000, 012 and 030 stay in the running.

Given the length of the password and the digits found by foresight, write a program that counts how many passwords are possible. A password consists only of the digits 0 through 9, and its first character may be 0.

Input

The first line contains the password length $n$ and the count $m$ of digits found by foresight, separated by a space. ( $1 \le n \le 7$ , $0 \le m \le n$ )

The second line contains the $m$ known digits, separated by spaces. Each digit is between 0 and 9, and they are distinct. If $m$ is 0, the second line is not given.

Output

Print the number of possible passwords.

Hint

If $n$ is 2 and the only known digit is 7, the possible passwords are 07, 17, 27, 37, 47, 57, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 87, 97, which is 19 in total.

If $n$ is 2 and the known digits are 3 and 4, the only possible passwords are 34 and 43.

Examples3

Example 1
Input
```
2 1
7
```
Expected output
```
19
```
Example 2
Input
```
2 2
3 4
```
Expected output
```
2
```
Example 3
Input
```
1 0
```
Expected output
```
10
```