I. Короткая задача о перестановке
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
Xomu - Last Dance
⠀

Вам дано целое число $$$n$$$.

Для каждой пары $$$(m, k)$$$ такой, что $$$3 \leq m \leq n+1$$$ и $$$0 \leq k \leq n-1$$$, посчитайте количество перестановок элементов $$$[1, 2, ..., n]$$$ таких, что $$$p_i + p_{i+1} \geq m$$$ для ровно $$$k$$$ индексов $$$i$$$, по модулю $$$998\,244\,353$$$.

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

Входные данные состоят из одной строки, которая содержит два целых числа $$$n$$$, $$$x$$$ ($$$2 \leq n \leq 4000$$$, $$$1 \leq x < 1\,000\,000\,007$$$).

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

Пусть $$$a_{m,k}$$$ - ответ для пары $$$(m, k)$$$, по модулю $$$998\,244\,353$$$.

Пусть $$$$$$\large S = \sum_{m=3}^{n+1} \sum_{k=0}^{n-1} a_{m,k}x^{mn+k}\phantom{0}.$$$$$$

Выведите единственную строку с целым числом: $$$S$$$ по модулю $$$1\,000\,000\,007$$$.

Обратите внимание, что использование двух разных модулей является намеренным. Мы хотим, чтобы вы вычислили все $$$a_{m,k}$$$ по модулю $$$998\,244\,353$$$, затем обработали их как целые числа в диапазоне $$$[0, 998\,244\,352]$$$, и хэшировали их по модулю $$$1\,000\,000\,007$$$.

Примеры
Входные данные
3 2
Выходные данные
77824
Входные данные
4 1000000000
Выходные данные
30984329
Входные данные
8 327869541
Выходные данные
85039220
Входные данные
4000 1149333
Выходные данные
584870166
Примечание

В первом примеры ответы для всех $$$(m, k)$$$ приведены в следующей таблице:

$$$k = 0$$$$$$k = 1$$$$$$k = 2$$$
$$$m = 3$$$$$$0$$$$$$0$$$$$$6$$$
$$$m = 4$$$$$$0$$$$$$4$$$$$$2$$$
  • Ответ для $$$(m, k) = (3, 2)$$$ равен $$$6$$$, потому что для каждой перестановки длины $$$3$$$, $$$a_i + a_{i+1} \geq 3$$$ ровно $$$2$$$ раза.
  • Ответ для $$$(m, k) = (4, 2)$$$ равен $$$2$$$. Действительно, существует $$$2$$$ перестановки длины $$$3$$$ такие, что $$$a_i + a_{i+1} \geq 4$$$ ровно $$$2$$$ раза: $$$[1, 3, 2]$$$, $$$[2, 3, 1]$$$.

Таким образом, значение для вывода равно $$$2^9 \cdot 0 + 2^{10} \cdot 0 + 2^{11} \cdot 6 + 2^{12} \cdot 0 + 2^{13} \cdot 4 + 2^{14} \cdot 2 \equiv 77\,824 \phantom{0} (\text{mod} \phantom{0} 1\,000\,000\,007)$$$.

Во втором примере ответы для всех $$$(m, k)$$$ приведены в следующей таблице:

$$$k = 0$$$$$$k = 1$$$$$$k = 2$$$$$$k = 3$$$
$$$m = 3$$$$$$0$$$$$$0$$$$$$0$$$$$$24$$$
$$$m = 4$$$$$$0$$$$$$0$$$$$$12$$$$$$12$$$
$$$m = 5$$$$$$0$$$$$$4$$$$$$16$$$$$$4$$$
  • Ответ для $$$(m, k) = (5, 1)$$$ — $$$4$$$. Действительно, существует $$$4$$$ перестановки длины $$$4$$$ такие, что $$$a_i + a_{i+1} \geq 5$$$ ровно $$$1$$$ раз: $$$[2, 1, 3, 4]$$$, $$$[3, 1, 2, 4]$$$, $$$[4, 2, 1, 3]$$$, $$$[4, 3, 1, 2]$$$.

В третьем примере ответы для всех $$$(m, k)$$$ представлены в следующей таблице:

$$$k = 0$$$$$$k = 1$$$$$$k = 2$$$$$$k = 3$$$$$$k = 4$$$$$$k = 5$$$$$$k = 6$$$$$$k = 7$$$
$$$m = 3$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$40320$$$
$$$m = 4$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$10080$$$$$$30240$$$
$$$m = 5$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$1440$$$$$$17280$$$$$$21600$$$
$$$m = 6$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$480$$$$$$8640$$$$$$21600$$$$$$9600$$$
$$$m = 7$$$$$$0$$$$$$0$$$$$$0$$$$$$96$$$$$$3456$$$$$$16416$$$$$$16896$$$$$$3456$$$
$$$m = 8$$$$$$0$$$$$$0$$$$$$48$$$$$$2160$$$$$$12960$$$$$$18240$$$$$$6480$$$$$$432$$$
$$$m = 9$$$$$$0$$$$$$16$$$$$$1152$$$$$$9648$$$$$$18688$$$$$$9648$$$$$$1152$$$$$$16$$$