#P15741. 第 K 小数字

第 K 小数字

题目描述

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

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

输入格式

第一行包含一个整数 QQ,表示询问数量。

接下来 QQ 行,每行包含 1111 个整数。前 1010 个整数依次表示数字 0,1,…,90,1,\ldots,9 的出现次数;最后一个整数是 KK。

对于每个询问,给定数字的总数严格大于 00 且不超过 7000070000。

输出格式

输出 QQ 行。第 ii 行输出第 ii 个询问的答案,即第 KK 小整数对 109+710^9+7 取模后的值。

数据范围

  • 1≤Q≤10001\le Q\le 1000;
  • 1≤K≤10121\le K\le 10^{12};
  • 每个询问中数字总数在 11 到 7000070000 之间。

样例 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