問題一覧 > 通常問題

No.1287 えぬけー

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 79
作問者 : tyawanmusityawanmusi / テスター : chineristACchineristAC
8 ProblemId : 5241 / 出題時の順位表
問題文最終更新日: 2020-11-14 19:20:12

問題文

整数 $X,K$ が与えられます。

$X = N^K\ \mathrm{mod}\ (10^9+7)$ となる整数 $N$ を求めて下さい。

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

制約

  • $X,K,T$ は整数
  • $1 \le T \le 10^5$
  • $0 \le X < 10^9+7$
  • $1 \le K \le 5 \times 10^8$
  • $K$ は奇数

入力

$T$

最初にテストケースの個数である整数 $T$ が $1$ 行に入力されます。

その後に、 $T$ 行に渡って次のように入力されます。

$X$ $K$

整数 $X,K$ が空白区切りで $1$ 行に入力されます。

出力

各テストケースについて、次のように出力してください。

整数 $N$ を $1$ 行に出力してください。最後に改行してください。

ここでの $N$ は、以下の制約を満たしている必要があります。

  • $0 \le N < 10^9+7$
  • $X = N^K\ \mathrm{mod}\ (10^9+7)$

与えられる入力及びこの制約において、解がただ一つ存在することが証明できます。

サンプル

サンプル1
入力
3
32 5
1000 3
4096 3
出力
2
10
16

$32 = 2^5$ , $1000 = 10^3$ , $4096 = 16^3$ です。

サンプル2
入力
3
1000000000 1
1000000000 3
1000000000 9
出力
1000000000
1000
10

$1000000000 = 1000000000^1$ , $1000000000 = 1000^3$ , $1000000000 = 10^9$ です。

サンプル3
入力
3
1000000006 11
1000000006 13
1000000006 15
出力
1000000006
1000000006
1000000006
サンプル4
入力
5
337716880 91488205
413500684 972383
499738548 34626483
901106148 239798535
230314780 62951413
出力
314159265
358979323
846264338
327950288
419716939

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。