题目描述

档案员栞手中有若干数字。对于每个询问，会给出数字 $0,1,\ldots,9$ 的出现次数，以及一个整数 $K$。你需要找到由这些数字恰好全部组成的整数中，第 $K$ 小的那个，并输出它对 $10^9+7$ 取模后的值。

注意，带前导零的整数也会被计入排序。例如，如果给定数字中有一个 0 和一个 1，那么 01 和 10 都会被计入，其中 01 表示的整数也按它的书写形式参与排列顺序。

输入格式

第一行包含一个整数 $Q$，表示询问数量。

接下来 $Q$ 行，每行包含 $11$ 个整数。前 $10$ 个整数依次表示数字 $0,1,\ldots,9$ 的出现次数；最后一个整数是 $K$。

对于每个询问，给定数字的总数严格大于 $0$ 且不超过 $70000$。

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案，即第 $K$ 小整数对 $10^9+7$ 取模后的值。

数据范围

• $1\le Q\le 1000$；
• $1\le K\le 10^{12}$；
• 每个询问中数字总数在 $1$ 到 $70000$ 之间。

样例 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
10
12
21
201
101