Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 4000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Difficulty Beta
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
Для отправки решений необходимо выполнить вход.
|