← 返回题目列表

Codeforces · 1626/F

F. 随机代码问题

中文机器翻译题面 查看原题

给定一个整数数组 $$$a_0, a_1, \dots, a_{n - 1}$$$ 和一个整数 $$$k$$$。您可以用它执行以下代码:

您的任务是在执行此代码后计算变量 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$$$ 在输入中给出;
- 对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$i$$$,$$$a_i$$$ 的值可以计算为 $$$a_i = (a_{i - 1} \cdot x + y) \bmod M$$$。

输出

令执行代码后变量 ans 的期望值为 $$$E$$$。可以证明 $$$E \cdot n^k$$$ 是一个整数。您必须输出该整数模 $$$998244353$$$。

示例

输入 #1

3 10 3 5 13 88

输出 #1

382842030

输入 #2

2 15363 270880 34698 17 2357023

输出 #2

319392398

注意

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