No.1287 NK

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 106
作問者 :

tyawanmusi / テスター :

chineristAC

お気に入りにしたユーザー ProblemId : 5241 / 自分の提出

問題文最終更新日: 2020-11-14 19:20:12

This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

yukicoder contest 274 (順位表) の他の問題:

Problem Statement

You are given integers $X,K$.

Find an integer $N$ such that $X = N^K\ \mathrm{mod}\ (10^9+7)$.

Answer for $T$ test cases.

Constraints

$X,K,T$ are integers
$1 \le T \le 10^5$
$0 \le X < 10^9+7$
$1 \le K \le 5 \times 10^8$
$K$ is odd

Input

$T$

First, an integer $T$, the number of test cases, is given on $1$ line.

Then, the following is given over $T$ lines.

$X$ $K$

The integers $X,K$ are given on $1$ line, separated by a space.

Output

For each test case, output as follows.

Output the integer $N$ on $1$ line. Print a newline at the end.

Here, $N$ must satisfy the following constraints.

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

It can be proved that, for the given input and these constraints, exactly one solution exists.

Sample

Sample 1

Input

Output

2
10
16

We have $32 = 2^5$ , $1000 = 10^3$ , $4096 = 16^3$ .

Sample 2

Input

3
1000000000 1
1000000000 3
1000000000 9

Output

1000000000
1000
10

We have $1000000000 = 1000000000^1$ , $1000000000 = 1000^3$ , $1000000000 = 10^9$ .

Sample 3

Input

3
1000000006 11
1000000006 13
1000000006 15

Output

1000000006
1000000006
1000000006

Sample 4

Input

5
337716880 91488205
413500684 972383
499738548 34626483
901106148 239798535
230314780 62951413

Output

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