Демодоги из Изнанки снова напали на Хоукинс. Оди хочет добраться до Майка и заодно уничтожить как можно больше демодогов по пути.
Хоукинс можно представить как клеточное поле \(n \times n\). Количество демодогов в клетке в \(i\)-й строке и \(j\)-м столбце равно \(i \cdot j\). Оди находится в позиции \((1, 1)\) и хочет достигнуть клетки \((n, n)\), где она найдет Майка.
Она может двигаться либо вправо (из \((i, j)\) в \((i, j + 1)\)), либо вниз (из \((i, j)\) в \((i + 1, j)\)). Она не может выходить за пределы поля, так как на его границах расположены двери в Изнанку.
Определите максимальное количество демодогов \(\mathrm{ans}\), которые Оди сможет уничтожить по пути, считая, что она уничтожает всех демодогов в клетках, которые посещает (включая стартовую и финишную).
Выведите \(2022 \cdot \mathrm{ans}\) по модулю \(10^9 + 7\). По модулю \(10^9 + 7\) потому, что результат может быть слишком большим, а умноженный на \(2022\) потому, что мы больше никогда его не увидим!
(Заметьте, вы сначала умножаете на \(2022\) и только потом берете остаток.)
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество демодогов, которое может быть уничтожено, умноженное на \(2022\) и по модулю \(10^9 + 7\).