在星舰 U.S.S. 的最新任务中编码员扬·比托夫斯基上尉意外传送到了一颗未知星球的表面。
为了找到回去的路,简发现了一件来自地球古代文明的神器——一种由 Byterola 创建的能够进行星际通话的移动设备。不幸的是,还有另一个问题。尽管简作为人类的代表,对手机号码的旧式表示法了如指掌,但设备键盘上的符号已经完全磨损,肉眼看不见。旧键盘恰好有 $$$m + 1$$$ 按钮,每个数字对应基本 $$$m$$$ 数字系统中的每个数字,还有一个退格按钮,允许用户删除最后写入的数字(如果屏幕上没有写入任何内容,则此按钮不会执行任何操作,但仍算作按下)。
Jan 想与他的工作人员沟通。他需要输入某个数字(也来自基本 $$$m$$$ 数字系统,即从 $$$0$$$ 到 $$$m - 1$$$ 的数字)。他想知道联系美国所需的预计按下按钮次数。编码员。 Jan 总是根据他当前的知识选择最优化的按钮。按钮在按下之前是无法区分的。帮助他!
输入
输入的第一行有两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$2 \le m \le 10^3$$$) — 到 U.S.S. 的号码长度编码器和数值系统的基础。
在下一个和最后一个输入行中,$$$0$$$ 和 $$$m - 1$$$ 之间有 $$$n$$$ 整数:在基本 $$$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}$$$。
示例
输入 #1
1 2 0
输出 #1
666666674
输入 #2
2 3 0 0
输出 #2
916666678
输入 #3
2 3 0 1
输出 #3
500000009
注意
在第一个示例中,键盘上有两个数字($$$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$$$ 按钮,然后需要用退格键将两个按钮删除,然后最后输入数字 $$$0$$$(总共按 5 次)。
我们得到 $$$\frac{16}{6}$$$ 的期望值。 $$$6$$$ 模 $$$1\;000\;000\;007$$$ 的模逆为 $$$166666668$$$,因此 $$$16 \cdot 166666668 = 666666674 \mod \; 1\;000\;000\;007$$$