Вам дано целое число \(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\).
Выходные данные
Пусть \(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\).
Примечание
В первом примеры ответы для всех \((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\) |
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
|
77824
|
|
2
|
4 1000000000
|
30984329
|
|
3
|
8 327869541
|
85039220
|
|
4
|
4000 1149333
|
584870166
|