|
Лимит времени 4000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Сложность Бета
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
Для отправки решений необходимо выполнить вход.
|