310451: CF1835E. Old Mobile

E. Old Mobiletime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

During the latest mission of the starship U.S.S. Coder, Captain Jan Bitovsky was accidentally teleported to the surface of an unknown planet.

Trying to find his way back, Jan found an artifact from planet Earth's ancient civilization — a mobile device capable of interstellar calls created by Byterola. Unfortunately, there was another problem. Even though Jan, as a representative of humans, knew perfectly the old notation of the cell phone numbers, the symbols on the device's keyboard were completely worn down and invisible to the human eye. The old keyboards had exactly $m + 1$ buttons, one for each digit from the base $m$ numerical system, and one single backspace button allowing one to erase the last written digit (if nothing was written on the screen, then this button does nothing, but it's still counted as pressed).

Jan would like to communicate with his crew. He needs to type a certain number (also from the base $m$ numerical system, that is, digits from $0$ to $m - 1$). He wants to know the expected number of button presses necessary to contact the U.S.S. Coder. Jan always chooses the most optimal buttons based on his current knowledge. Buttons are indistinguishable until pressed. Help him!

Input

In the first line of input, there are two integer numbers $n$ and $m$ ($1 \le n \le 10^6$, $2 \le m \le 10^3$) — the length of the number to U.S.S. Coder and the base of the numerical system.

In the next and the last input line, there are $n$ integers between $0$ and $m - 1$: the number to type in the base $m$ numerical system.

Output

Output the expected number of button presses modulo $1\,000\,000\,007$.

Formally, let $M = 1\,000\,000\,007$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.

ExamplesInput

1 2
0

Output

666666674

Input

2 3
0 0

Output

916666678

Input

2 3
0 1

Output

500000009

Note

In the first example, two digits ($0$ and $1$) and a backspace button are available on the keyboard. Jan has no way of knowing which one is which, so he presses a random one.

With probability $\frac{1}{3}$, he presses $0$ and manages to type the crew's number.

With probability $\frac{1}{3}$, he presses backspace, and nothing happens. Then with probability $\frac{1}{2}$ he manages to press $0$ (finishing the process). Otherwise, with probability $\frac{1}{2}$, he types $1$, which he then needs to remove with backspace and hit the last button, which has to be $0$. In this case, he needs $4$ button presses.

At last, he might press the $1$ button first, also with probability $\frac{1}{3}$. Then, if he presses the backspace with a chance of $50\%$, he is all set and only needs to press the last button (3 presses in total). In the worst case, he would press the $0$ button first and need to remove both with backspace, then finally type the number $0$ (5 presses in total).

We get the expected value of $\frac{16}{6}$. The modular inverse of $6$ modulo $1\;000\;000\;007$ is $166666668$, so $16 \cdot 166666668 = 666666674 \mod \; 1\;000\;000\;007$

题目大意：
星际飞船U.S.S. Coder的最新任务中，船长Jan Bitovsky意外被传送到一个未知星球的表面。为了找到返回的方法，Jan发现了一个来自地球古代文明的艺术品——一个能够进行星际通话的移动设备，由Byterola公司制造。不幸的是，有一个问题，尽管作为人类代表的Jan非常了解旧式手机号码的表示法，但设备键盘上的符号已经完全磨损，无法被肉眼看到。旧键盘上有恰好$m+1$个按钮，每个按钮对应于基数为$m$的数字系统中的一个数字，以及一个单独的退格按钮，允许用户擦除最后一个输入的数字（如果屏幕上没有数字，则此按钮无效，但仍算作被按下）。

Jan想要与他的船员沟通。他需要输入一个特定的数字（也来自基数为$m$的数字系统，即从$0$到$m-1$的数字）。他想知道联系U.S.S. Coder所需的预期按键次数。Jan总是根据他当前的知识选择最合适的按钮。在按下之前，按钮是不可区分的。帮助他！

输入输出数据格式：
输入：
第一行输入两个整数$n$和$m$（$1 \le n \le 10^6$，$2 \le m \le 10^3$）——要输入的数字长度和数字系统的基数。
下一行（也是最后一行）输入$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}$。

请注意，以上是对题目大意的翻译，具体的公式和示例没有翻译。题目大意： 星际飞船U.S.S. Coder的最新任务中，船长Jan Bitovsky意外被传送到一个未知星球的表面。为了找到返回的方法，Jan发现了一个来自地球古代文明的艺术品——一个能够进行星际通话的移动设备，由Byterola公司制造。不幸的是，有一个问题，尽管作为人类代表的Jan非常了解旧式手机号码的表示法，但设备键盘上的符号已经完全磨损，无法被肉眼看到。旧键盘上有恰好$m+1$个按钮，每个按钮对应于基数为$m$的数字系统中的一个数字，以及一个单独的退格按钮，允许用户擦除最后一个输入的数字（如果屏幕上没有数字，则此按钮无效，但仍算作被按下）。 Jan想要与他的船员沟通。他需要输入一个特定的数字（也来自基数为$m$的数字系统，即从$0$到$m-1$的数字）。他想知道联系U.S.S. Coder所需的预期按键次数。Jan总是根据他当前的知识选择最合适的按钮。在按下之前，按钮是不可区分的。帮助他！ 输入输出数据格式： 输入： 第一行输入两个整数$n$和$m$（$1 \le n \le 10^6$，$2 \le m \le 10^3$）——要输入的数字长度和数字系统的基数。 下一行（也是最后一行）输入$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}$。 请注意，以上是对题目大意的翻译，具体的公式和示例没有翻译。