Дан массив целых чисел \(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 после выполнения этого кода.
Обратите внимание, что входные данные генерируется специальным образом (подробнее в секции «Входные данные»).
Выходные данные
Пусть матожидание значения переменной ans после выполнения кода равно \(E\). Можно показать, что \(E \cdot n^k\) — целое число. Выведите остаток от деления этого числа на \(998244353\).
Примечание
Массив в первом примере — \([10, 35, 22]\). Во втором примере — \([15363, 1418543]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 10 3 5 13 88
|
382842030
|
|
2
|
2 15363 270880 34698 17 2357023
|
319392398
|