给定一些数字。你的任务是找到由给定的数字组成的第 $K$ 小的整数，结果对 $10^9 + 7$ 取模。你需要回答 $Q$ 个询问（每个询问包含数字的频率和一个整数 $K$）。

注意，包含前导零的整数也计入考虑范围。

输入格式

第一行包含一个整数 $Q$ ($1 \le Q \le 5000$)。

接下来的 $Q$ 行，每行包含 11 个整数。前十个整数表示数字 $0, 1, \dots, 9$ 的频率。最后一个整数是 $K$ ($1 \le K \le 10^{12}$)。对于每个询问，数字的总数严格大于 0 且不超过 $70\,000$。

输出格式

输出 $Q$ 行。第 $i$ 行必须包含一个整数：第 $i$ 个询问的答案对 $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