Дан массив целых чисел \(a_0, a_1, \dots, a_{n - 1}\) и целое число \(k\). Вы выполняете следующий код:
long long ans = 0; // 64-битная знаковая целочисленная переменная, изначально равная 0for(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\).
Массив в первом примере — \([10, 35, 22]\). Во втором примере — \([15363, 1418543]\).
3 10 3 5 13 88
382842030
2 15363 270880 34698 17 2357023
319392398
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач