Given $n$ digit strings, each containing only digits from 0 to 9. You need to perform $k$ swap operations. Each operation consists of choosing any two different positions across all strings and swapping the digits at those positions. After the swap operations, calculate the sum of the products of the $n$ strings when converted to integers, considering all possible outcomes.

Note: The positions chosen for each swap operation are independent, and it is allowed to choose the same two positions in two different swap operations.

Input

The first line contains two integers $n$ and $k$.

The next $n$ lines each contain a digit string $s_i$. It is guaranteed that the strings only contain digits 0 to 9.

Output

Output a single integer representing the answer. Since the answer can be very large, output the result modulo $10^9 + 7$.

Examples

Input 1

1 2
12
34

Output 1

3740

Note 1

After one swap operation, there are 6 possible outcomes for the two strings: 1. 21, 34 2. 12, 43 3. 32, 14 4. 42, 31 5. 13, 24 6. 14, 32

The final answer is: $21 \cdot 34 + 12 \cdot 43 + 32 \cdot 14 + 42 \cdot 31 + 13 \cdot 24 + 14 \cdot 32 = 3740$

Input 2

2 2
1
12

Output 2

165

Note 2

After two swap operations, there are 9 possible outcomes for the two strings: 1. 1, 12 2. 2, 11 3. 1, 21 4. 1, 21 5. 1, 12 6. 2, 11 7. 2, 11 8. 1, 21 9. 1, 12

The final answer is: $1 \cdot 12 + 2 \cdot 11 + 1 \cdot 21 + 1 \cdot 21 + 1 \cdot 12 + 2 \cdot 11 + 2 \cdot 11 + 1 \cdot 21 + 1 \cdot 12 = 165$

Examples 3-8

For examples 3 through 8, please refer to the files swap/swap3.in through swap/swap8.in and their corresponding .ans files in the contestant directory. These examples satisfy the constraints for the corresponding test cases.

Constraints

For all test data, it is guaranteed that $1 \le n \le 100$, $1 \le k \le 10^9$, $1 \le |s_i| \le 10^7$, and $2 \le \sum |s_i| \le 10^7$.

Special Property A: The strings only contain the digits 1 and 2.