Дан массив целых чисел $$$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$$$ строится следующим образом:
Пусть матожидание значения переменной 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]$$$.
Название |
---|