F. Случайный код
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив целых чисел $$$a_0, a_1, \dots, a_{n - 1}$$$ и целое число $$$k$$$. Вы выполняете следующий код:

long long ans = 0; // 64-битная знаковая целочисленная переменная, изначально равная 0
for(int i = 1; i <= k; i++)
{
  int idx = rnd.next(0, n - 1); // генерирует случайное целое число от 0 до n - 1 включительно
                                // каждое целое число от 0 до n - 1 выбирается с одинаковой вероятностью
  ans += a[idx];
  a[idx] -= (a[idx] % i);
}

Ваша задача — посчитать матожидание значения переменной ans после выполнения этого кода.

Обратите внимание, что входные данные генерируется специальным образом (подробнее в секции «Входные данные»).

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

В единственной строке заданы шесть целых чисел $$$n$$$, $$$a_0$$$, $$$x$$$, $$$y$$$, $$$k$$$ и $$$M$$$ ($$$1 \le n \le 10^7$$$; $$$1 \le a_0, x, y < M \le 998244353$$$; $$$1 \le k \le 17$$$).

Массив $$$a$$$ строится следующим образом:

  • $$$a_0$$$ задано во входных данных;
  • для каждого $$$i$$$ от $$$1$$$ до $$$n - 1$$$ значение $$$a_i$$$ считается как $$$a_i = (a_{i - 1} \cdot x + y) \bmod M$$$.
Выходные данные

Пусть матожидание значения переменной ans после выполнения кода равно $$$E$$$. Можно показать, что $$$E \cdot n^k$$$ — целое число. Выведите остаток от деления этого числа на $$$998244353$$$.

Примеры
Входные данные
3 10 3 5 13 88
Выходные данные
382842030
Входные данные
2 15363 270880 34698 17 2357023
Выходные данные
319392398
Примечание

Массив в первом примере — $$$[10, 35, 22]$$$. Во втором примере — $$$[15363, 1418543]$$$.