Это сложная версия задачи. Разница заключается в ограничениях на \(n\), \(m\) и \(t\). Делать взломы можно только в том случае, если решены обе задачи.
Алисе и Бобу даются числа \(n\), \(m\) и \(k\), и они играют в следующую игру:
В игре есть счет, который Алиса пытается максимизировать, а Боб старается минимизировать. Первоначально счет равен \(0\). Игра состоит из \(n\) ходов. Каждый ход Алиса выбирает число от \(0\) до \(k\) (необязательно целое), которое Боб либо прибавляет, либо вычитает из счета игры. Но на протяжении всей игры Боб должен прибавить не менее \(m\) из \(n\) ходов.
Боб узнает, какое число выбрала Алиса, прежде чем решит, прибавить или вычесть это число из счета, а Алиса узнает, прибавил Боб или вычел число для предыдущего хода, прежде чем выбрать число для текущего хода (кроме первого хода, поскольку предыдущего хода не было).
Если Алиса и Боб будут играть оптимально, каков будет окончательный счет игры?
Выходные данные
Для каждого тестового примера выведите одно число — результат оптимальной игры по модулю \(10^9 + 7\).
Формально пусть \(M = 10^9 + 7\). Можно показать, что ответ может быть выражен в виде неприводимой дроби \(\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}\).
Примечание
В первом тестовом примере вся игра имеет \(3\) хода, и, поскольку \(m = 3\), Боб должен добавить в каждый из них. Следовательно, Алиса должна каждый ход выбирать самое большое число, которое она может, а именно \(k = 2\).
В третьем тестовом примере у Алисы есть стратегия, гарантирующая оценку \(\frac{75}{8} \equiv 375000012 \pmod{10^9 + 7}\).
В четвертом тестовом примере у Алисы есть стратегия, гарантирующая оценку \(\frac{45}{2} \equiv 500000026 \pmod{10^9 + 7}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 3 2
2 1 10
6 3 10
6 4 10
100 1 1
4 4 0
69 4 20
|
6
5
375000012
500000026
958557139
0
49735962
|