YOU: "The banners are lovely. You were in charge of those?"

MARCUS: "Sure was. It's nice when someone actually appreciates the real, human effort that goes into these things. Nobody does anymore."

YOU: "If the banners were already made, why were you here helping set up?"

MARCUS: "Kevin asked me to help Ritisha put them up. Found her the best spots, held the step-ladder steady. Safety first."

YOU: "Did you talk to anyone else that afternoon?"

MARCUS: "Nah, just Ritisha, the entire time. She's great company, didn't feel like I needed to talk to anyone else. Think she needed it, too. She was down about having her responsibility taken off her. That's a bit typical for this club."

Marcus has been working on ACPC Ball banners for twelve hours straight, and he is beginning to go a bit loopy. He has an array of ~n~ numbers ~a_1, \ldots, a_n~, where ~a_i~ is the number of copies of banner ~i~ that Marcus needs to make. Sadly, on such little sleep, Marcus begins to feel gripped by many emotions.

Marcus Feels Happy

First, each value ~a_i~ is replaced by its happiness value ~h_i~. The happiness value of a positive integer ~a_i~ is the number of integers that have between ~1~ and ~a_i~ digits (inclusive), where no digit appears a strict majority number of times.

More specifically, a number with ~\ell~ digits qualifies if and only if every digit value appears at most ~\left\lfloor \frac\ell2 \right\rfloor~ times. Numbers with leading zeros do not qualify.

Each happiness value is taken modulo ~214112929~.

For instance, the happiness values for ~a_i = 1, 2, 3, 4, 5, 6~ are ~0, \; 81, \; 729, \; 9396, \; 91692, \; 980262~.

Marcus Feels Sad

Next, each value is split into its digits. A number with ~\ell~ digits becomes ~\ell~ single-digit elements in the array.

For instance, ~h_i = 9396~ contributes the four elements ~9, 3, 9, 6~ to the array. A value with fewer digits contributes fewer elements; ~h_i = 0~ contributes the single element ~0~.

Marcus feels Angry

Finally, the digits skitter around. Marcus counts the number of distinct permutations of the array with at most ~k~ inversions. For some array ~D~, an inversion is a pair of positions ~p < q~ where ~D_p > D_q~. Permutations that differ only by swapping equal digits are identical in this step.

Output this final count modulo ~214112929~.

For instance, the array ~1, 2, 3~ has ~2~ arrangements with ~1~ inversion, ~1, 3, 2~ and ~2, 1, 3~.

Input

The first line contains two integers, ~n~ and ~k~ (~1 \leq n \leq 10^3, 0 \leq k \leq 10^4~), the length of Marcus' initial array and his inversion-counting limit.

The second line contains ~n~ integers ~a_1, \ldots, a_n~ (~1 \leq a_i \leq 10^3~), the values in Marcus' initial array.

Output

Output Marcus' final value after feeling happy, then sad, then angry, modulo ~214112929~.

Example

Input 1

4 2
1 2 1 3

Output 1

21

Marcus Feels Happy

• There are ~0~ numbers of length ~1~ with no digits appearing more than ~1/2 = 0~ times.
• There are ~81~ numbers of length ~2~ with no digits appearing more than ~2/2 = 1~ time.
• There are ~729~ numbers of length ~3~ with no digits appearing more than ~3/2 = 2~ times.

Therefore, when Marcus feels happy, his array becomes 0, 81, 0, 729.

Marcus Feels Sad

Splitting by digits, Marcus' array becomes 0, 8, 1, 0, 7, 2, 9.

Marcus Feels Angry

There are ~21~ arrangements of 0, 8, 1, 0, 7, 2, 9 with at most ~k = 2~ inversions:

• 0, 0, 1, 2, 7, 8, 9
• 0, 0, 1, 2, 7, 9, 8
• 0, 0, 1, 2, 8, 7, 9
• 0, 0, 1, 7, 2, 8, 9
• 0, 0, 2, 1, 7, 8, 9
• 0, 1, 0, 2, 7, 8, 9
• 0, 0, 1, 2, 8, 9, 7
• 0, 0, 1, 2, 9, 7, 8
• 0, 0, 1, 7, 2, 9, 8
• 0, 0, 1, 7, 8, 2, 9
• 0, 0, 1, 8, 2, 7, 9
• 0, 0, 2, 1, 7, 9, 8
• 0, 0, 2, 1, 8, 7, 9
• 0, 0, 2, 7, 1, 8, 9
• 0, 0, 7, 1, 2, 8, 9
• 0, 1, 0, 2, 7, 9, 8
• 0, 1, 0, 2, 8, 7, 9
• 0, 1, 0, 7, 2, 8, 9
• 0, 1, 2, 0, 7, 8, 9
• 0, 2, 0, 1, 7, 8, 9
• 1, 0, 0, 2, 7, 8, 9

Input 2

2 1
10 10

Output 2

5

Marcus Feels Happy

• There are ~128912009~ numbers of length ~10~ with no digits appearing more than ~10/2 = 5~ times.

Therefore, when Marcus feels happy, his array becomes 128912009, 128912009.

Marcus Feels Sad

Splitting by digits, Marcus' array becomes 1, 2, 8, 9, 1, 2, 0, 0, 9, 1, 2, 8, 9, 1, 2, 0, 0, 9.

Marcus Feels Angry

There are ~5~ arrangements of 1, 2, 8, 9, 1, 2, 0, 0, 9, 1, 2, 8, 9, 1, 2, 0, 0, 9 with at most ~k = 1~ inversion:

• 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 8, 8, 9, 9, 9, 9
• 0, 0, 0, 0, 1, 1, 1, 2, 1, 2, 2, 2, 8, 8, 9, 9, 9, 9
• 0, 0, 0, 0, 1, 1, 1, 1, 2, 1, 2, 2, 8, 8, 9, 9, 9, 9
• 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 8, 9, 8, 9, 9, 9
• 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 8, 8, 9, 9, 9, 9

Input 3

10 10
1 2 3 4 5 6 7 8 9 10

Output 3

1055872