C. Простое число
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Семена есть простое число 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.