題敘

在一個風和日麗的午後，筱丑一如往常地沉迷於她最喜歡的糞 game。這款遊戲充滿了各種誇張的數值膨脹、難以理解的機制，但她依然樂此不疲，特別是她最愛的角色——擁有最帥氣技能特效的 SSR 級英雄。

然而，每當她興奮地點開對戰模式，迎來的卻總是——敗北。

「為什麼？明明練等那麼久了！」 筱丑氣得摔鍵盤，卻發現一個殘酷的現實—她根本不會計算角色的攻擊力！

已知道每個角色都有個天賦值a，角色基礎攻擊力滿足下列多項式：

${\Large{x^2}+ax+1=0}$

x的解(取正數)就是角色的基礎攻擊力。 同時角色的等級也會影響攻擊力(n為角色等級，上限為100等)，計算公式如下：

${\Large f(n) = x^{2^n} + x^{-2^n}}$

計算出的f(n)就是最終的攻擊力。 這意味著，等級越高，攻擊力的變化就越誇張！現在，請幫筱丑計算出她最愛角色的最終攻擊力，讓她能夠擊敗對手，成功翻盤

輸入

第1行有一正整數$t$代表接下來有t行輸入， 第2~t+1行每行輸入兩整數$a$, $n$

範圍

$1 ~{\le}~ n ~{\le}~ 100 \\$ $30\%$測資：$~t ~{\le}~ 2~{\times}~10^3,~-10^9 ~{\le}~ a ~{\le}~ 10^9 \\$ $60\%$測資：$~t ~{\le}~ 2~{\times}~10^5,~-10^9 ~{\le}~ a ~{\le}~ 10^9 \\$ $100\%$測資：$~t ~{\le}~ 2~{\times}~10^6,~-10^{18} ~{\le}~ a ~{\le}~ 10^{18}$

輸出

輸出 ${ f(n)~mod~10^9 + 7}$ 的值

範例輸入

3
5 2
-3 3
2 114514

527
2207
2