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 0

for(int i = 1; i 
                            

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 < 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 $ .

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 $ .

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