给定一个整数数组 $$$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]$$$。