E. Старый мобильник
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время последней миссии звездолета U.S.S. Coder капитан Ян Битовский был случайно телепортирован на поверхность неизвестной планеты.

Пытаясь найти обратную дорогу, Ян обнаружил артефакт древней цивилизации планеты Земля — мобильное устройство, способное осуществлять межзвездные звонки, созданное компанией Byterola. К сожалению, возникла другая проблема. Хотя Ян, как представитель людей, прекрасно знал старую нотацию номеров мобильных телефонов, символы на клавиатуре устройства были полностью стерты и невидимы человеческому глазу. На старых клавиатурах было ровно $$$m + 1$$$ кнопок, по одной на каждую цифру из системы счисления по основанию $$$m$$$, и одна кнопка backspace, позволяющая стереть последнюю написанную цифру (если на экране ничего не написано, то эта кнопка ничего не делает, но она нажатие все равно считается).

Ян хочет связаться со своей командой. Ему нужно набрать определенное число (также из системы счисления по основанию $$$m$$$, то есть цифры от $$$0$$$ до $$$m - 1$$$). Он хочет знать математическое ожидание количества нажатий на кнопки, необходимое для связи с кораблем U.S.S. Coder. Ян всегда выбирает наиболее оптимальные кнопки с учетом своих текущих знаний. Кнопки неразличимы до тех пор, пока не будут нажаты.

Помогите ему!

Входные данные

В первой строке ввода находятся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$2 \le m \le 10^3$$$), разделенные одним пробелом — длина номера U.S.S. Coder и основание системы счисления.

Во второй строке находятся $$$n$$$ целых чисел от $$$0$$$ до $$$m - 1$$$: номер, который должен набрать Ян Битовский, в системе счисления по основанию $$$m$$$.

Выходные данные

Выведите ожидаемое количество нажатий на кнопки по модулю $$$1\,000\,000\,007$$$.

Формально, пусть $$$M = 1\,000\,000\,007$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Примеры
Входные данные
1 2
0
Выходные данные
666666674
Входные данные
2 3
0 0
Выходные данные
916666678
Входные данные
2 3
0 1
Выходные данные
500000009
Примечание

В первом примере на клавиатуре имеются две цифры ($$$0$$$ и $$$1$$$) и кнопка backspace. Ян не может знать, какая из них какая, поэтому он нажимает случайную.

С вероятностью $$$\frac{1}{3}$$$ он нажимает $$$0$$$ и ему удается набрать номер экипажа.

С вероятностью $$$\frac{1}{3}$$$ он нажимает backspace, и ничего не происходит. Затем с вероятностью $$$\frac{1}{2}$$$ ему удается нажать $$$0$$$ (завершая процесс). В противном случае, с вероятностью $$$\frac{1}{2}$$$, он набирает $$$1$$$, который затем должен удалить с помощью backspace и нажать последнюю кнопку, которая должна быть $$$0$$$. В этом случае ему потребуется $$$4$$$ нажатий на кнопку.

Наконец, он может нажать сначала кнопку $$$1$$$, также с вероятностью $$$\frac{1}{3}$$$. Затем, если он нажмет backspace с вероятностью $$$50\%$$$, то все будет готово и ему останется только нажать последнюю кнопку (всего 3 нажатия). В худшем случае, он нажмет сначала кнопку $$$0$$$ и должен будет удалить обе с помощью backspace, а затем, наконец, набрать число $$$0$$$ (всего 5 нажатий).

Мы получаем ожидаемое значение $$$\frac{16}{6}$$$. Обратное к $$$6$$$ по модулю $$$1\;000\;000\;007$$$ равно $$$166666668$$$, поэтому $$$16 \cdot 166666668 = 666666674 \mod \; 1\;000\;000\;007$$$.