题目内容

客服系统里最初只有一张额度为 $n$ 的主工单。每一秒，当前集合中的所有工单同时按同一规则拆分：对额度 $x$，会生成两张额度为 $\lfloor x/2 \rfloor+1$ 的子工单；若 $x$ 为奇数，还会额外生成一张额度为 2 的子工单。原工单随即移除。同一秒内所有拆分基于该秒开始时的集合同时发生，互不影响。

求经过 $m$ 秒后所有工单额度的总和。答案可能很大，对 1000000007 取模。

约束：测试组数不超过 10000，$n$ 与 $m$ 均不超过 1000000000。

输入描述

第一行一个整数 $T$，表示测试组数，满足 $1 \le T \le 10000$。 接下来 $T$ 行，每行两个整数 $n$ 和 $m$，满足 $1 \le n,m \le 1000000000$。

输出描述

对每组数据输出一行一个整数，表示 $m$ 秒后所有工单额度之和对 1000000007 取模的结果。

样例1

输入

3
2 4
5 1
8 3

输出

32
8
32

说明

$n=2$ 时 $f(2,m)=2^{m+1}$，故 $f(2,4)=32$。 $n=5$ 为奇数，裂变 1 秒后和为 8。 $n=8$ 裂变 3 秒后和为 32。

样例2

输入

1
7 5

输出

128

说明

从 $n=7$ 开始裂变 5 秒。按奇偶递推并套用 $f(1,m)=(m+1)2^m$、$f(2,m)=2^{m+1}$，答案为 128。

样例3

输入

2
3 2
9 1

输出

12
12

说明

$n=3$ 为奇数，会多出一个 2，两秒后总和为 12。 $n=9$ 裂变 1 秒：$b=5$，总和为 $2\times 5+2=12$。