Вам дано положительное целое число \(k\) и массив \(a_1, a_2, \ldots, a_n\) неотрицательных различных чисел от \(k\) до \(2^c-1\).
В каждую из следующих \(k\) секунд один элемент выбирается случайно равновероятно из всех \(n\) элементов и уменьшается на \(1\).
Для каждого целого числа \(x\), \(0 \leq x \leq 2^c - 1\), вам нужно найти вероятность, что в конце побитовый XOR всех чисел в массиве равен \(x\).
Каждое из этих значений может быть представлено в виде несократимой дроби \(\frac{p}{q}\), и вам нужно найти \(p \cdot q^{-1}\) по модулю \(998\,244\,353\).
Выходные данные
Выведите \(2^c\) целых чисел: вероятность, что побитовой XOR в конце равен \(x\), для всех \(x\) среди \(\{0, 1, \ldots, 2^c-1\}\) по модулю \(998\,244\,353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1 3
1 2 3 4
|
0 0 0 748683265 0 499122177 0 748683265
|