У Семена есть простое число x и массив целых неотрицательных чисел a1, a2, ..., an.
Семен очень любит дроби. Сегодня он записал на листок число 
. После того, как Семен привел все дроби к общему знаменателю и сложил их, он получил дробь: 
, где число t равно xa1 + a2 + ... + an. Теперь Семен хочет сократить полученную дробь.
Помогите ему, найдите наибольший общий делитель s и t. Так как НОД может быть довольно большим, требуется найти лишь его остаток от деления на число 1000000007 (109 + 7).
Выходные данные
Выведите единственное число — ответ на задачу по модулю 1000000007 (109 + 7).
Примечание
В первом примере 
. Таким образом, ответ на задачу 8.
В втором примере 
. Ответ на задачу 27, так как 351 = 13·27, 729 = 27·27.
В третьем примере ответ на задачу 1073741824 mod 1000000007 = 73741817.
В четвертом примере 
. Таким образом, ответ на задачу 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
2 2
|
8
|
|
2
|
3 3
1 2 3
|
27
|
|
3
|
2 2
29 29
|
73741817
|
|
4
|
4 5
0 0 0 0
|
1
|