問題文

正整数 $N$, $M$ が与えられます。ただし、$M$ は偶数とします。

$1$ 以上 $N^{M}$ 以下の整数 $x$ のうち、次のように定義される $f(x)$ に対して $f(x) > \sqrt{x}$ を満たすものの総和を求めてください。

• $x$ の正の約数の中央値を $f(x)$ とする。

  厳密には、$x$ の正の約数の個数を $k$ とし、$x$ の正の約数すべてを値の小さい順に並べ替えたものを $a_{1}, a_{2}, \dots, a_{k}$ として、$f(x)$ を次のように定義する。

  • $\displaystyle f(x) := \left\{ \begin{array}{l} \displaystyle a_{ \frac{ k + 1 }{ 2 } } \text{ （$k$ が奇数のとき）} \\ \displaystyle \frac{ 1 }{ 2 } \left( a_{ \frac{ k }{ 2 } } + a_{ \frac{ k + 2 }{ 2 } } \right) \text{ （$k$ が偶数のとき）} \\ \end{array} \right.$

答えは非常に大きくなる可能性があるので、$10^{9}+7$ で割った余りを出力してください。

$T$ 個のテストケースについて答えを求めてください。

制約

• $1 \leq T \leq 10^{5}$

• $1 \leq N, M \leq 10^{9}$

• $T$, $N$ は整数

• $M$ は偶数

入力

まず、$1$ 行目にはテストケースの個数 $T$ が与えられます。

$T$

続けて $T$ 個のテストケースがそれぞれ次の形式で与えられます。

$N$ $M$

$(i+1)$ $(1 \leq i \leq T)$ 行目には、$i$ 個目のテストケースにおける $N$ と $M$ の値がこの順に半角スペース区切りで与えられます。

出力

答えを $1$ 行ずつ合計 $T$ 行に出力し、最後に改行してください。

$i$ $(1 \leq i \leq T)$ 行目には、$i$ 個目のテストケースにおける答えを出力してください。

サンプル

10
2 2
9 4
1 13815080
5694830 3748
15 3220
173991719 37288
7 37682
13868805 2400766
37236186 5850
1181 334

5
21346200
0
630387477
322736621
782465690
423690148
362798159
283023473
859877451