E. Задачка на комбинаторику
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Напомним, что биномиальный коэффициент $$$\binom{x}{y}$$$ вычисляется следующим образом ($$$x$$$ и $$$y$$$ — неотрицательные целые числа):

  • если $$$x < y$$$, то $$$\binom{x}{y} = 0$$$;
  • в противном случае $$$\binom{x}{y} = \frac{x!}{y! \cdot (x-y)!}$$$.

Дан массив $$$a_1, a_2, \dots, a_n$$$ и целое число $$$k$$$. Вам нужно вычислить новый массив $$$b_1, b_2, \dots, b_n$$$, где

  • $$$b_1 = (\binom{1}{k} \cdot a_1) \bmod 998244353$$$;
  • $$$b_2 = (\binom{2}{k} \cdot a_1 + \binom{1}{k} \cdot a_2) \bmod 998244353$$$;
  • $$$b_3 = (\binom{3}{k} \cdot a_1 + \binom{2}{k} \cdot a_2 + \binom{1}{k} \cdot a_3) \bmod 998244353$$$, и так далее.

Формально, $$$b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j) \bmod 998244353$$$.

Обратите внимание, что массив задан в измененном виде, и вы должны вывести его в измененном виде.

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

В единственной строке ввода содержатся шесть целых чисел $$$n$$$, $$$a_1$$$, $$$x$$$, $$$y$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n \le 10^7$$$; $$$0 \le a_1, x, y < m$$$; $$$2 \le m \le 998244353$$$; $$$1 \le k \le 5$$$).

Массив $$$[a_1, a_2, \dots, a_n]$$$ генерируется следующим образом:

  • $$$a_1$$$ задан во входных данных;
  • для $$$2 \le i \le n$$$, $$$a_i = (a_{i-1} \cdot x + y) \bmod m$$$.
Выходные данные

Поскольку вывод $$$10^7$$$ целых чисел может быть слишком медленным, вы должны выполнить следующее:

Пусть $$$c_i = b_i \cdot i$$$ (без взятия остатка от деления на $$$998244353$$$ после умножения). Выведите целое число $$$c_1 \oplus c_2 \oplus \dots \oplus c_n$$$, где $$$\oplus$$$ обозначает оператор побитового исключающего ИЛИ.

Пример
Входные данные
5 8 2 3 100 2
Выходные данные
1283