解题思路

设经过 $m$ 秒后的答案为 $f(n,m)$。

题目中的分裂规则是：

• 若当前数字为偶数 $a$，会分裂成两个数字 $\left\lfloor \dfrac{a}{2} \right\rfloor + 1$；
• 若当前数字为奇数 $a$，除了上面的两个数字外，还会额外分裂出一个数字 $2$。

题目内容

给定一个初始值为 $n$ 的数字。

每一秒，当前所有的数字都会同时执行分裂操作：

• 记分裂的数字为 $x$，它会分裂成两个数字：$⌊x/2⌋+1$ 和 $⌊x/2⌋+1$；此外，如果 $x$ 为奇数，它还会额外分裂出一个数字 $2$。

• 操作结束后，原数字 $x$ 被移除，仅保留新生成的数字，且所有数字的分裂基于该秒开始时的集合同时进行，不受其它分裂顺序影响。

求经过 $m$ 秒后，所有数字的总和。由于答案可能很大，请将结果对 ($10^9+7$) 取模后输出。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数，每组测试数据描述如下：

在一行上输入两个整数 $n,m(1≤n,m≤10^9)$。

输出描述

对于每组测试数据，新起一行，输出一个整数，表示最终结果对 ($10^9+7$) 取模后的值。

样例1

输入

2
1 3
11 2

输出

32
20