시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 0 0 0 0.000%

문제

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$.

예제 입력 1

6
1 1 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0 2
1 1 1 0 0 0 0 0 0 0 1
1 1 1 0 0 0 0 0 0 0 2
1 1 1 0 0 0 0 0 0 0 5
1 2 0 0 0 0 0 0 0 0 2

예제 출력 1

1
10
12
21
201
101