По кругу расставлены \(m\) корзин, пронумерованных от \(1\) до \(m\) по часовой стрелке (корзина \(m\) находится рядом с корзиной \(1\)). Кроме того, имеется \(n\) шаров, причем шар \(i\) первоначально помещен в корзину \(a_i\), и ни одна корзина не содержит более одного шара.
Алисе разрешено выполнять следующую операцию, которая всегда занимает ровно одну секунду, независимо от того, перемещаете/выбрасываете вы шар или нет:
- Алиса выбирает целое число \(i\) между \(1\) и \(n\) равномерно случайным образом.
- Если шар \(i\) был выброшен ранее, ничего не делать.
- В противном случае, шар \(i\) перемещается из корзины, в которой он находится в данный момент, в следующую корзину (по часовой стрелке). Если в корзине, в которую перемещается шар, сейчас находится другой шар \(j\), выбросить шар \(j\).
Она повторяет эту операцию до тех пор, пока не останется ровно один шар. Вычислите математическое ожидание времени (в секундах), необходимого Алисе для завершения процесса.
Можно доказать, что ответ можно представить в виде рационального числа \(\frac{p}{q}\) с простыми \(p\) и \(q\). Вам нужно вывести \(p \cdot q^{-1} \bmod 10^9 + 7\). Можно доказать, что \(10^9 + 7 \nmid q\).
Выходные данные
Для каждого набора входных данных выведите одно целое число: математическое ожидание времени (в секундах), необходимое Алисе для завершения процесса, по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных Алиса могла бы действовать следующим образом (мы определяем \(a_i = -1\), если шар \(i\) был выброшен):
- Изначально \(a = [5, 1, 4]\).
- Алиса выбирает \(i = 2\) с вероятностью \(\frac{1}{3}\), и шар \(2\) перемещается в корзину \(2\). После этого \(a = [5, 2, 4]\).
- Алиса выбирает \(i = 2\) с вероятностью \(\frac{1}{3}\), и шар \(2\) перемещается в корзину \(3\). После этого \(a = [5, 3, 4]\).
- Алиса выбирает \(i = 2\) с вероятностью \(\frac{1}{3}\), и шар \(2\) перемещается в корзину \(4\). Поскольку в корзине \(4\) ранее находился шар \(3\), этот шар выбрасывается. После этого \(a = [5, 4, -1]\).
- Алиса выбирает \(i = 3\) с вероятностью \(\frac{1}{3}\). Шар \(3\) уже был выброшен, поэтому ничего не происходит. После этого \(a = [5, 4, -1]\).
- Алиса выбирает \(i = 2\) с вероятностью \(\frac{1}{3}\), и шар \(2\) перемещается в корзину \(5\), из которой выбрасывается шар \(1\). После этого \(a = [-1, 5, -1]\), и процесс завершается.
Ответ для этого набора входных данных равен
\(\frac{189}{5}\).
Ответ для второго набора входных данных равен \(14\) (обратите внимание, что эти два шара находятся рядом друг с другом).
Ответ для третьего набора входных данных равен \(35\).
Ответ для четвертого набора входных данных равен \(\frac{220}{3}\).
В пятом наборе входных данных, поскольку изначально имеется только один шар, ответ равен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 10
5 1 4
2 15
15 1
6 6
1 2 3 4 5 6
6 9
6 5 4 3 2 1
1 100
69
|
600000042
14
35
333333409
0
|