Эта задача такая же как и предыдущая, но с большими ограничениями.
Аки играет в новую видео-игру. В этой игре он управляет Неко, огромным котом, способным перемещаться между планетами кошковселенной.
Кошковселенная состоит из \(n\) планет, пронумерованных от \(1\) до \(n\). В начале игры Аки выбирает планету, на которой изначально находится Неко. Затем Аки совершает \(k - 1\) ходов, где за один ход Аки перемещает Неко с текущей планеты \(x\) на какую-то планету \(y\), такую что:
- Планета \(y\) ещё не посещена.
- \(1 \leq y \leq x + m\) (где \(m\) это фиксированная константа, заданная во входных данных)
Таким образом Неко посетит ровно \(k\) различных планет. Два способа посещений планет называются различными, если существует индекс \(i\), что \(i\)-я планета в первом способе отличается от \(i\)-й планеты во втором способе.
Сколько всего существует способов посетить \(k\) планет таким образом? Так как ответ может быть достаточно большим, выведите его по модулю \(10^9 + 7\).
Выходные данные
Выведите ровно одно целое число — количество способов, которыми Неко может посетить \(k\) планет. Так как это число может быть достаточно большим, выведите его по модулю \(10^9 + 7\).
Примечание
В первом примере есть \(4\) способа для Неко посетить все планеты:
- \(1 \rightarrow 2 \rightarrow 3\)
- \(2 \rightarrow 3 \rightarrow 1\)
- \(3 \rightarrow 1 \rightarrow 2\)
- \(3 \rightarrow 2 \rightarrow 1\)
Во втором примере есть \(9\) способов посетить ровно \(2\) планеты:
- \(1 \rightarrow 2\)
- \(2 \rightarrow 1\)
- \(2 \rightarrow 3\)
- \(3 \rightarrow 1\)
- \(3 \rightarrow 2\)
- \(3 \rightarrow 4\)
- \(4 \rightarrow 1\)
- \(4 \rightarrow 2\)
- \(4 \rightarrow 3\)
В третьем примере \(m = 4\) и Неко может посетить все планеты в любом порядке, так что всего есть \(5! = 120\) способов всё посетить.
В четвёртом примере Неко должен посетить только \(1\) планету (которая в частности будет начальной планетой маршрута), а значит есть \(100\) способов посетить одну планету.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 1
|
4
|
|
2
|
4 2 1
|
9
|
|
3
|
5 5 4
|
120
|
|
4
|
100 1 2
|
100
|