F. A Random Code Problemtime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou 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).InputThe 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. OutputLet 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.ExamplesInput
3 10 3 5 13 88
Output
382842030
Input
2 15363 270880 34698 17 2357023
Output
319392398
NoteThe array in the first example test is [10, 35, 22]. In the second example, it is [15363, 1418543].
3 10 3 5 13 88

382842030 
['combinatorics', 'dp', 'math', 'number theory', 'probabilities', '*2800']