Placing Cards

Interview

Time limit1sMemory limit256 MB

Summary

Given up to 10 cards with 1 or 2 digit numbers, count the distinct integers formed by ordering exactly k chosen cards.

Level: Easy3 of 10
Topics: Brute force, Backtracking, Hash map, Implementation
Solved: No attempts yet

Problem

Sanggeun lays $n$ cards ( $4 \le n \le 10$ ) side by side on the floor. Each card has a single integer from $1$ to $99$ written on it. He wants to choose $k$ ( $2 \le k \le 4$ ) of the cards and line them up from left to right in the chosen order to form a single integer. How many different integers can he make?

For example, suppose there are 5 cards showing 1, 2, 3, 13, 21. If he picks 3 of them, then laying out 2, 1, 13 in that order gives 2113, and laying out 21, 1, 3 in that order also gives 2113. Because different choices can produce the same integer, you must count only the distinct integers.

Given the numbers written on the $n$ cards, write a program that finds how many different integers can be formed by choosing $k$ of them.

Input

The first line contains the number of cards $n$ , and the second line contains the number of cards to choose $k$ . Each of the next $n$ lines contains the number written on one card.

Output

Print the number of different integers Sanggeun can make on the first line.

Hint

When the four cards are $1, 2, 12, 1$ and $k = 2$ , Sanggeun can make the 7 integers $11, 12, 21, 112, 121, 122, 212$ .

Examples2

Example 1
Input
```
4
2
1
2
12
1
```
Expected output
```
7
```
Example 2
Input
```
6
3
72
2
12
7
2
1
```
Expected output
```
68
```