D2. Игра на сумму (Сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Разница заключается в ограничениях на $$$n$$$, $$$m$$$ и $$$t$$$. Делать взломы можно только в том случае, если решены обе задачи.

Алисе и Бобу даются числа $$$n$$$, $$$m$$$ и $$$k$$$, и они играют в следующую игру:

В игре есть счет, который Алиса пытается максимизировать, а Боб старается минимизировать. Первоначально счет равен $$$0$$$. Игра состоит из $$$n$$$ ходов. Каждый ход Алиса выбирает число от $$$0$$$ до $$$k$$$ (необязательно целое), которое Боб либо прибавляет, либо вычитает из счета игры. Но на протяжении всей игры Боб должен прибавить не менее $$$m$$$ из $$$n$$$ ходов.

Боб узнает, какое число выбрала Алиса, прежде чем решит, прибавить или вычесть это число из счета, а Алиса узнает, прибавил Боб или вычел число для предыдущего хода, прежде чем выбрать число для текущего хода (кроме первого хода, поскольку предыдущего хода не было).

Если Алиса и Боб будут играть оптимально, каков будет окончательный счет игры?

Входные данные

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество тестов. Описание тестовых примеров следует ниже.

Каждый тестовый пример состоит из одной строки, содержащей три целых числа: $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le m \le n \le 10^6, 0 \le k < 10^9 + 7$$$) — количество ходов, сколько из этих ходов Боб должен прибавить, и наибольшее число, которое Алиса может выбрать соответственно.

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$10^6$$$.

Выходные данные

Для каждого тестового примера выведите одно число — результат оптимальной игры по модулю $$$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}$$$.

Пример
Входные данные
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
Примечание

В первом тестовом примере вся игра имеет $$$3$$$ хода, и, поскольку $$$m = 3$$$, Боб должен добавить в каждый из них. Следовательно, Алиса должна каждый ход выбирать самое большое число, которое она может, а именно $$$k = 2$$$.

В третьем тестовом примере у Алисы есть стратегия, гарантирующая оценку $$$\frac{75}{8} \equiv 375000012 \pmod{10^9 + 7}$$$.

В четвертом тестовом примере у Алисы есть стратегия, гарантирующая оценку $$$\frac{45}{2} \equiv 500000026 \pmod{10^9 + 7}$$$.