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