題目描述

我們定義一個關於幂的函數 𝑓(𝑥) = 𝑥^x，並且對於任意正整數 𝑁，

𝑆(𝑁) = f(2⁰) + f(2¹) + f(2²) + ... + f(2^N)

𝑆₁(𝑁) = f(N⁰) + f(N¹) + f(N²) + ... + f(N^N)

輸入格式

第一行一個正整數 𝑇，表示接下來有 𝑇 個測試用例。

每個測試用例一行，兩個正整數 𝑁, 𝑀。

對於每個測試用例，進行以下判斷：

當 𝑀 為 1 時，輸出 𝑆(𝑁) 𝑚𝑜𝑑 1000000007 的值。

當 𝑀 為 2 時，輸出 𝑆₁ (𝑁) 𝑚𝑜𝑑 1000000007 的值。

每個測試用例的輸出資料需以隔行分隔。

5 
261 
356223755

數據範圍

[10 分, 1.0𝑠] 測試數據 1~10: 𝑇 ≤ 10, 𝑁 ≤ 10, 𝑀 ≤ 1。

[15 分, 1.0𝑠] 測試數據 11~15: 𝑇 ≤ 50, 𝑁 ≤ 200, 𝑀 ≤ 2。

[15 分, 1.0𝑠] 測試數據 16~20: 𝑇 ≤ 100, 𝑁 ≤ 10⁴ , 𝑀 ≤ 2。