CF1835E.Old Mobile
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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!
输入格式
In the first line of input, there are two integer numbers n and m ( 1≤n≤106 , 2≤m≤103 ) — 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 the expected number of button presses modulo 1000000007 .
Formally, let M=1000000007 . It can be shown that the answer can be expressed as an irreducible fraction qp , where p and q are integers and q≡0(modM) . Output the integer equal to p⋅q−1modM . In other words, output such an integer x that 0≤x<M and x⋅q≡p(modM) .
输入输出样例
输入#1
1 2 0
输出#1
666666674
输入#2
2 3 0 0
输出#2
916666678
输入#3
2 3 0 1
输出#3
500000009
说明/提示
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 31 , he presses 0 and manages to type the crew's number.
With probability 31 , he presses backspace, and nothing happens. Then with probability 21 he manages to press 0 (finishing the process). Otherwise, with probability 21 , 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 31 . 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 616 . The modular inverse of 6 modulo 1000000007 is 166666668 , so 16⋅166666668=666666674mod1000000007