시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 256 MB | 1 | 1 | 1 | 100.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$.
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 10 12 21 201 101