CSES 1095 ↗

Exponentiation

`a^b` modulo `10^9 + 7`, with `0^0 = 1`.

1
submissions
1.000
best score

Your task is to efficiently calculate values ab modulo 109+7.

Note that in this task we assume that 00=1.

Input

The first input line contains an integer n: the number of calculations.

After this, there are n lines, each containing two integers a and b.

Output

Print each value ab modulo 109+7.

Constraints

  • 1≤n≤2⋅105
  • 0≤a,b≤109

Example

Input:

3
3 4
2 8
123 123

Output:

81
256
921450052

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/Exponentiation/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
869,790,080869,790,080

1 qualifying submission. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.000869,790,080talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-25 11:58 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.