#XMOJ10262. 花圃编号牌

花圃编号牌

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:number.in 输出文件:number.out

佳佳的爸爸在花圃里做事,花圃的每个花盆上都插着一块小木牌,牌子上写着一个数字,这就是这盆花的编号。

今天早上,爸爸把一盆花交给佳佳照顾,并且定下了「每月一换」的规矩:每到月初,佳佳要把花盆上的所有木牌按同样的办法更新一遍——牌子上写的数字往前跳一格,0跳成1,1跳成2,一直跳到8跳成9;而写着9的木牌已经跳到头了,佳佳就把它取下来,换成两块新木牌,一块写1、一块写0,按左边1、右边0的顺序插回原来的位置。旁边插着什么、插了几块,都不妨碍一块木牌自己怎么变。

举个例子:编号是1912的花盆插着四块木牌,换过一次之后,这四块木牌依次变成2、1和0、2、3,从左到右连起来读是21023,一共五块木牌。

爸爸想知道:编号为 $n$ 的花盆,经过 $m$ 个月以后,一共插着多少块木牌?木牌数目可能很大,你只需要输出它对 $10^9+7$ 取模的结果。

输入格式

第一行一个整数 $T$,表示询问的组数。

接下来 $T$ 行,每行两个整数 $n$、$m$,分别表示这盆花的初始编号和经过的月数。

输出格式

输出 $T$ 行,每行一个整数,表示对应询问中经过 $m$ 个月后花盆上的木牌数目对 $10^9+7$ 取模的结果。

样例

样例 1

3
1912 1
999 1
12 2
5
6
2

样例说明:

第一组:四块木牌分别跳成2、1和0、2、3,连起来读是21023,共 55 块。

第二组:三块都写着9的木牌,各自被换成1和0两块,共 $6$ 块。

第三组:两块木牌分别是1和2,一个月后变成2和3,再一个月后变成3和4,共 $2$ 块。

样例 2

3
5 6
88 2
12 100
2
4
2115

样例说明:

第一组:编号5只有一块木牌,66 个月后变成21,共 22 块。

第二组:两块都写着8的木牌,第一个月都跳成9,第二个月各自被换成1和0两块,共 $4$ 块。

第三组:经过 $100$ 个月后,木牌总数对 $10^9+7$ 取模的结果是 $2115$。

样例 3

3
1 1
9 1
1000000000 1
1
2
10

样例说明:

第一组:编号1的木牌跳成了2,仍然是 11 块。

第二组:编号9的木牌被换成1和0两块。

第三组:编号1000000000一共十块木牌,其中没有写着9的,一个月后还是十块。

数据范围

$1 \le T \le 1000$。

$1 \le n \le 10^9$,$1 \le m \le 2 \times 10^5$。

对于 $50\%$ 的测试点,$1 \le T \le 100$,$1 \le m \le 100$。

对于 $100\%$ 的测试点,$1 \le T \le 1000$,$1 \le m \le 2 \times 10^5$。