Problem description

Podczas najnowszej misji statku U.S.S. Coder, kapitan Jan Bitovsky, został omyłkowo przeteleportowany na powierzchnię nieznanej dotąd planety.

Szukając sposobu na komunikację ze swoją załogą, Jan odnalazł prastary artefakt starożytnej cywilizacji Ziemi – urządzenie mobilne zdolne do połączeń międzyplanetarnych firmy Bajtorola. Niestety, pojawił się kolejny problem. Mimo że Jan, jako przedstawiciel rasy ludzkiej, doskonale zna dawny sposób zapisu numerów komórkowych, oznaczenia na klawiaturze urządzenia są już zupełnie nieczytelne. Wiadomo jedynie, że na klawiaturze znajduje się dokładnie M przycisków z cyframi w systemie o bazie M oraz jeden przycisk usunięcia ostatnio napisanego znaku (jeżeli na ekranie nie ma napisanej żadnej cyfry, to przycisk ten nic nie robi).

Jan chciałby zadzwonić do swojej załogi, do czego potrzebuje wpisać odpowiedni numer (jest on również złożony z cyfr w systemie o bazie M, czyli cyfr od 0 do M − 1). Zastanawia się, ile wynosi oczekiwana liczba kliknięć w klawiaturę, zakładając, że Jan zawsze wybiera optymalnie przyciski w danej sytuacji oraz klawisze są nierozróżnialne, dopóki nie zostaną wciśnięte. Pomóż mu!

Wejście

W pierwszym wierszu wejścia dane są dwie liczby naturalne N i M oddzielone pojedynczym odstępem, oznaczające kolejno długość numeru do załogi Jana Bitovsky’ego oraz bazę systemu liczbowego, do jakiego należą cyfry z numeru oraz klawiatury urządzenia. W drugim i ostatnim wierszu wejścia znajduje się N oddzielonych pojedynczymi odstępami liczb całkowitych – numer, który potrzeba wpisać.

Wyjście

Na wyjściu program powinien wypisać jedną liczbę całkowitą W taką, że W = P ⋅ Q⁻¹ mod  1 000 000 007, gdzie $\frac{P}{Q}$ oznacza oczekiwaną liczbę kliknięć koniecznych do wpisania numeru przez Jana, a Q⁻¹ mod  1 000 000 007 oznacza odwrotność modularną liczby Q modulo 1 000 000 007.

Ograniczenia

1 ≤ N ≤ 1 000 000, 2 ≤ M ≤ 1 000, liczby oznaczające numer są z przedziału od 0 do M − 1.

Przykład

1 2
0

666666674

Wyjaśnienie przykładu

W przykładzie są dwie cyfry (0 i 1) oraz trzeci przycisk cofania. Jan nie wie, który to który, więc przyciska dowolny z nich.

• Z prawdopodobieństwem $\frac{1}{3}$ przyciśnie on 0 i uda mu się wpisać numer do załogi.
• Również z prawdopodobieństwem $\frac{1}{3}$ przyciśnie on cofanie i nic się nie stanie. Wtedy z prawdopodobieństwem $\frac{1}{2}$ uda mu się wybrać 0. W przeciwnym razie wciśnie klawisz 1, który potem musi usunąć i wybrać ostatni pozostały przycisk, którym musi być 0. W tym scenariuszu potrzebował by 4 wciśnięć.
• Finalnie, z prawdopodobieństwem $\frac{1}{3}$ może wcisnąć jako pierwszy przycisk 1. Wtedy, jeśli jako drugi wciśnie przycisk cofania, to będzie potrzebował już tylko wybrać ostatni przycisk (w sumie trzy wciśnięcia). W najgorszym przypadku, jeśli wciśnie 0 jako drugie, to będzie potrzebował dwukrotnie użyć cofania zanim wpisze poprawny numer (łącznie 5 wciśnięć).

Łącznie otrzymujemy wartość oczekiwaną $\frac{1}{3} + \big( 2 \cdot \frac{1}{6} + 4 \cdot \frac{1}{6} \big) + \big( 3 \cdot \frac{1}{6} + 5 \cdot \frac{1}{6} \big) = \frac{16}{6}$. Odwrotność modularna 6 modulo 1 000 000 007 to 166666668, więc 16 ⋅ 166666668 = 666666674 mod  1 000 000 007.