神神又奇奇 时间限制：3500 ms

空间限制：512 MiB

题目描述 定义一个整数是“神奇”的，当且仅当这个数的每一位要么是 1，要么是 2，例如 22,12211,1111111 都是“神奇”的，但是 3,210,1064 则不是。

现在给定一个数 X（保证 X 是“神奇”的），假设所有 ≤X 且位数与 X 相同的所有数中所有“神奇”的数从小到大排列分别是 a1,a2,⋯,ak，再额外给定一整数 t，你需要求出： 如果 k<t，则认为答案为 0。

由于这个数可能非常大，因此你只需要求它对 109+7 取模以后的结果即可。

输入格式 第一行包含一个整数 T 表示测试数据组数。

接下来 T 行每行两个整数 X,t。

输出格式 对于每个测试数据输出一个数，表示答案对 109+7 取模后的结果。

样例 样例输入 #1 7 22 4 112 2 2122 2 21122 1 22221122 10 222222222 2 111111211 10 样例输出 #1 60984 12432 25556522 271130 589578886 737317456 0 数据范围与提示 对于 100% 的数据，保证 1≤T≤10，X≤1030000，1≤t≤10，保证 X 都是“神奇”的.

测试点编号 X< t 特殊性质 1∼2 106 ≤10 无 3∼5 1018 ≤10 无 6∼7 101000 =1 无 8∼9 1030000 =1 无 10∼11 1030000 =2 有 12∼14 101000 =2 无 15∼18 1030000 =2 无 19∼21 1030000 ≤10 有 22∼25 1030000 ≤10 无 特殊性质：保证 X 只由数码 2 组成。