CF1626F.A Random Code Problem

You are given an integer array $a_0, a_1, \dots, a_{n - 1}$, and an integer $k$. You perform the following code with it:

long long ans = 0; // create a 64-bit signed variable which is initially equal to 0for(int i = 1; i <= k; i++){  int idx = rnd.next(0, n - 1); // generate a random integer between 0 and n - 1, both inclusive                                // each integer from 0 to n - 1 has the same probability of being chosen  ans += a[idx];  a[idx] -= (a[idx] % i);}

Your task is to calculate the expected value of the variable ans after performing this code.

Note that the input is generated according to special rules (see the input format section).

给你一个整数数组 $a_0, a_1, \dots, a_{n - 1}$ 和一个整数 $k$。你将对它执行以下代码：

long long ans = 0; // 创建一个初始值为 0 的 64 位有符号变量
for(int i = 1; i <= k; i++){
  int idx = rnd.next(0, n - 1); // 在区间 $[0, n - 1]$ 内生成一个随机整数（含端点）
                                // 区间内每个整数被选中的概率均等
  ans += a[idx];
  a[idx] -= (a[idx] % i);
}

你的任务是计算执行完该代码后变量 ans 的期望值。

注意：输入数据是根据特殊规则生成的（参见“输入格式”部分）。

The only line contains six integers $n$, $a_0$, $x$, $y$, $k$ and $M$ ($1 \le n \le 10^7$; $1 \le a_0, x, y \lt M \le 998244353$; $1 \le k \le 17$).

The array $a$ in the input is constructed as follows:

• $a_0$ is given in the input;
• for every $i$ from $1$ to $n - 1$, the value of $a_i$ can be calculated as $a_i = (a_{i - 1} \cdot x + y) \bmod M$.

唯一一行包含六个整数 $n$、$a_0$、$x$、$y$、$k$ 和 $M$（$1 \le n \le 10^7$；$1 \le a_0, x, y \lt M \le 998244353$；$1 \le k \le 17$）。

输入中的数组 $a$ 按如下方式构造：

• $a_0$ 由输入给出；
• 对每个从 $1$ 到 $n - 1$ 的 $i$，$a_i$ 的值按公式 $a_i = (a_{i - 1} \cdot x + y) \bmod M$ 计算。

Let the expected value of the variable ans after performing the code be $E$. It can be shown that $E \cdot n^k$ is an integer. You have to output this integer modulo $998244353$.

令执行代码后变量 ans 的期望值为 $E$。可以证明 $E \cdot n^k$ 是一个整数。你需要输出该整数对 $998244353$ 取模的结果。

The array in the first example test is $[10, 35, 22]$. In the second example, it is $[15363, 1418543]$.

第一个示例测试中的数组为 $[10, 35, 22]$。第二个示例中的数组为 $[15363, 1418543]$。