题目描述:

此题为困难版本,本问题hard和easy版本的区别为n,k的范围以及有无多组输入输出

由于本题的运行量较大,评测环境请选择C++17(O2)进行评测,避免被卡常

曾经有一个这样的故事广为流传: 说的是一个国王要赏赐一个大臣，就让他自己提一个方案。大臣说：“我的要求不高，只要在棋盘的第一个格子里装1粒米，第二个格子里装2粒，第三个格子装4粒，第四个格子装8粒，以此类推，直到把64个格子装完。”国王一听，暗暗发笑，要求太低了，照办！ 这个故事的结局相信每一个人都知道,所有的米的总和为$\sum_{i=1}^{64}2^{i}$,这个问题太简单啦,用小学数学就可以直接计算出来总和.

故事中的国王经过了上次的教训之后,决定报复一下那位大臣,苦思冥想后想出了一道类似的问题. 现在有一个$n*n$的棋盘,假设每一个格子的坐标为$(i,j)$,那么每一个格子所需放的米的数量为$(i+j)^k$,问想放满所有棋盘格子所需的米的总数是多少.即求出

这下大臣犯了难,如果答不出来这个问题将会被迫与这个世界告别,现在他来求助你,希望你能解决这个问题. 因为这个问题的答案可能很大,所以你最终的答案需要对1e9+7取模再输出

输入格式:

本题具有多组输入,第一行一个$T$,表示接下来的输入数据总数

接下来$T$行,每一行输入两个正整数$n,k$,表示有一个$n*n$的棋盘,以及$k$次幂

输出格式:

输出$T$行,每一行表示对应的需要的米的数量

输入输出样例:

输入#1

1
3 2

输出#2

156

输入#2

2
3 2 
10 5

输出#2

156
41642150

数据范围:

对于$100\%$的测试点保证,$T\in[1,10],$$n\in[1,1e7],k\in[1,1e7]$,且保证$\sum{n}<3e7,\sum{k}<3e7$