Iris is playing with oql's keyboard again.

Over a period of $T$ days, each day Iris types several characters on oql's keyboard, and these characters happen to be exactly the 10 Arabic digits from $0$ to $9$. Statistics show that there are $a_i$ occurrences of the digit $i$.

Every day, oql decides to feed Iris a certain amount of cat food. He decides to choose $m$ digits from the $\sum_{i=0}^9 a_i$ available digits and rearrange them to form an $m$-digit decimal non-negative integer $x$ that does not contain a leading zero. Then, oql will feed Iris $x$ grams of cat food that day.

However, Iris is still a kitten and should not eat too much cat food. Therefore, oql wants to make this number as small as possible. Please help Iris calculate how much cat food she gets each day.

Since the answer can be very large, you only need to output the result modulo $10^9 + 7$. Please note that you need to output the result of the minimum answer modulo $10^9 + 7$, not the minimum value of $x \pmod{10^9 + 7}$.

Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), representing the number of days.

For the next $T$ lines, each line contains 11 space-separated non-negative integers $m, a_0, a_1, \dots, a_9$ ($1 \le m \le 10^9, 0 \le a_i \le 10^9$), representing the situation for each day.

The data guarantees that a solution exists, meaning it is always possible to form at least one $m$-digit non-negative integer without a leading zero.

Output

For each day, output a single integer representing the result of the amount of cat food Iris gets that day, modulo $10^9 + 7$.

Examples

Input 1

3
3 1 0 0 0 3 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0 0
4 0 1 1 1 3 0 0 0 0 0

Output 1

404
0
1234