Qnp

Time limit1.5sMemory limit256 MB

Summary

For each query, find the K-th smallest arrangement of the given digit counts (leading zeros allowed), modulo 10^9 + 7, with K up to 10^12.

Level: Medium7 of 10
Topics: Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

You are given some digits. Find the $K$ -th smallest integer that consists of exactly the given digits, modulo $10^9 + 7$ . Answer $Q$ queries. Each query gives the frequencies of digits $0$ , $1$ , $\ldots$ , $9$ , followed by an integer $K$ .

Integers with leading zeroes are also counted.

Input

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 are the frequencies of digits $0$ , $1$ , $\ldots$ , $9$ . The last one is the integer $K$ ( $1 \le K \le 10^{12}$ ). In each query, the total number of digits is at least 1 and at most $70000$ .

Output

Print $Q$ lines. The $i$ -th line contains the answer for the $i$ -th query modulo $10^9 + 7$ .

Examples1

Example 1

Input

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

Expected output