Qnp

You are given some digits. Your task is to find the $K$-th smallest integer that consists of exactly the digits given, modulo $10^9 + 7$. You should answer $Q$ such queries (a query consists of digit frequencies and an integer $K$).

Note that integers with leading zeroes are also taken into account.

The first line contains a single integer $Q$ ($1 \le Q \le 5000$).

Each of the next $Q$ lines contains $11$ integers. The first ten denote the frequencies of digits $0$, $1$, $\ldots$, $9$. The last one is the integer $K$ ($1 \le K \le 10^{12}$). For each query, the total number of digits is strictly positive and does not exceed $70\\,000$.

Print $Q$ lines. The $i$-th line must contain one integer: the answer for the $i$-th query modulo $10^9 + 7$.