Old Mobile
Contest: Codeforces Round 880 (Div. 1)
Difficulty rating: 3500
Tags: combinatorics, dp, probabilities

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 format:
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 format:
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}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$

Example input:
1 2
0

Example output:
666666674

Example input:
2 3
0 0

Example output:
916666678

Editorial:
Let us make some observations. First of them is that if a phone number consists of two or more digits of the same kind then we will always pay exactly $$$1$$$ click for each but the first occurrence of it (it follows from the fact, that we have to already the key responsible for this digit). This is why we can reduce the problem to finding a solution for a phone number with unique digits.
Secondly, since all the buttons are indistinguishable at the beginning then the order of digits in the input does not matter.
This leads to the conclusion that what we want to compute is some kind of $$$dp[i][j]$$$, which stands for expected time of completing number if $$$i$$$ buttons that we have to eventually click are not yet discovered (good buttons), and $$$j$$$ buttons that we don't need are also not yet discovered (bad buttons). Unfortunately the BackSpace key and necessity of clearing incorrect prefix of the phone number complicates things significantly.
We will create additional dimension of the $$$dp$$$ responsible for the state of the prefix and the information about if we have already clicked backspace. Those four states will be:
• $$$EMPTY$$$ – empty prefix of digits on the screen
• $$$GOOD$$$ – non empty, correct prefix of digits on the screen
• $$$BAD$$$ – non empty prefix that is not prefix of the phone number
• $$$BACKSPACE$$$ – when we have already found a backspace (we assume prefix is correct, or in other words paid in advance)
Let us first compute $$$dp[i][j][BACKSPACE]$$$. If $$$i = 0$$$ then $$$dp[0][j][BACKSPACE] = 0$$$. Else we try to click new buttons. If we guess correctly exactly the next button then we get $$$dp[i][j][BACKSPACE] = 1 + dp[i - 1][j][BACKSPACE]$$$. Otherwise we could guess one of the remaining good buttons (with probability $$$\frac{i - 1}{i + j}$$$. Since we already know backspace location, we can remove it and in future we will pay only $$$1$$$ for this digit. We hence get $$$3 + dp[i - 1][j][BACKSPACE]$$$ operations. Similarly if we guess bad button we get $$$dp[i][j][BACKSPACE] = 2 + dp[i][j - 1][BACKSPACE]$$$.
Rest of the states can be computed using similar approach: $$$$$$ dp[i][j][GOOD]= \begin{cases} 0, & \text{if } i = 0 \\ 1 + dp[i - 1][j][GOOD], & \text{when tossing exactly correct digit} \\ 3 + dp[i - 1][j][BAD], & \text{for one of the remaining good digits} \\ & \text{(in future we will have to remove it and use in correct place)} \\ 2 + dp[i][j - 1][BAD], & \text{for guessing bad digit} \\ 2 + dp[i][j][BACKSPACE], & \text{when clicking backspace button} \\ & \text{(removing good digit from the prefix which we need to fix)} \end{cases} $$$$$$
$$$$$$ dp[i][j][BAD]= \begin{cases} 3 + dp[i - 1][j][BAD], & \text{when guessing any good digit} \\ 2 + dp[i][j - 1][BAD], & \text{for bad digit} \\ dp[i][j][BACKSPACE], & \text{when clicking backspace} \\ & \text{(this click was paid in advance)} \end{cases} $$$$$$
$$$$$$ dp[i][j][EMPTY]= \begin{cases} 1 + dp[i - 1][j][GOOD], & \text{when tossing correct digit} \\ 3 + dp[i - 1][j][BAD], & \text{when guessing other good digit} \\ 2 + dp[i][j - 1][BAD], & \text{for bad digit} \\ 1 + dp[i][j][BACKSPACE], & \text{when clicking backspace} \end{cases} $$$$$$
Even though transitions may look scary, they are similar for different dimensions and common implementation can be used.