CF1835E.Old Mobile

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!

在星际飞船“美国星舰程序员号”（U.S.S. Coder）最近的一次任务中，詹·比特沃斯基船长意外地被传送到了一颗未知行星的表面。

为了设法返回，詹发现了一件来自地球古代文明的遗物——一部由拜特罗拉公司（Byterola）制造、具备星际通话能力的移动设备。不幸的是，还有另一个问题：尽管詹作为人类代表，对旧式手机号码的记法了如指掌，但该设备键盘上的所有符号均已完全磨损，肉眼无法辨识。旧式键盘恰好有 $m + 1$ 个按键：其中 $m$ 个分别对应 $m$ 进制数字系统中的每个数字（即从 $0$ 到 $m - 1$），另有一个单独的退格键（backspace），用于删除屏幕上最后输入的一个数字（若屏幕为空，则该按键无效，但仍计为一次按键）。

詹希望与他的船员取得联系。他需要输入一个特定的号码（该号码同样属于 $m$ 进制数字系统，即仅由 $0$ 至 $m - 1$ 的数字组成）。他想知道：为成功联系上“美国星舰程序员号”，所需按键次数的期望值是多少？詹总是依据当前所掌握的信息，选择最优的按键策略。在按键被按下之前，所有按键彼此不可区分。请帮助他！

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.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^6$，$2 \le m \le 10^3$）——分别表示要输入的数字的长度以及该数字所使用的进制。

接下来且最后一行输入包含 $n$ 个介于 $0$ 和 $m - 1$ 之间的整数：表示该数字在 $m$ 进制下的各位数字。

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 \lt M$ and $x \cdot q \equiv p \pmod{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$。换言之，输出满足 $0 \le x \lt M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

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$

在第一个例子中，键盘上有两个数字键（$0$ 和 $1$）以及一个退格键。Jan 无法分辨哪个键对应什么功能，因此他随机按下一个键。

以概率 $\frac{1}{3}$，他按下 $0$，成功输入船员编号。

以概率 $\frac{1}{3}$，他按下退格键，此时无任何效果；随后以概率 $\frac{1}{2}$ 他成功按下 $0$（完成输入）；否则，以概率 $\frac{1}{2}$ 他输入了 $1$，接着需用退格键将其删除，再按下最后一个键（该键必须是 $0$）。此情况下，他共需 $4$ 次按键。

最后，他可能首先按下 $1$ 键，其概率也为 $\frac{1}{3}$。此时，若他以 $50\%$ 的概率按下退格键，则任务完成，仅需再按一次最后一个键（总计 $3$ 次按键）；最坏情况下，他会先按下 $0$ 键，然后需用退格键连续删除两个字符（即 $1$ 和 $0$），最后再输入 $0$（总计 $5$ 次按键）。

最终得到期望值为 $\frac{16}{6}$。模 $1\;000\;000\;007$ 意义下 $6$ 的模逆元为 $166666668$，因此 $16 \cdot 166666668 = 666666674 \mod \; 1\;000\;000\;007$。