Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

combinatorics

dp

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Combinatorics Problem

time limit per test

4 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputRecall that the binomial coefficient $$$\binom{x}{y}$$$ is calculated as follows ($$$x$$$ and $$$y$$$ are non-negative integers):

- if $$$x < y$$$, then $$$\binom{x}{y} = 0$$$;
- otherwise, $$$\binom{x}{y} = \frac{x!}{y! \cdot (x-y)!}$$$.

You are given an array $$$a_1, a_2, \dots, a_n$$$ and an integer $$$k$$$. You have to calculate a new array $$$b_1, b_2, \dots, b_n$$$, where

- $$$b_1 = (\binom{1}{k} \cdot a_1) \bmod 998244353$$$;
- $$$b_2 = (\binom{2}{k} \cdot a_1 + \binom{1}{k} \cdot a_2) \bmod 998244353$$$;
- $$$b_3 = (\binom{3}{k} \cdot a_1 + \binom{2}{k} \cdot a_2 + \binom{1}{k} \cdot a_3) \bmod 998244353$$$, and so on.

Formally, $$$b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j) \bmod 998244353$$$.

Note that the array is given in a modified way, and you have to output it in a modified way as well.

Input

The only line of the input contains six integers $$$n$$$, $$$a_1$$$, $$$x$$$, $$$y$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n \le 10^7$$$; $$$0 \le a_1, x, y < m$$$; $$$2 \le m \le 998244353$$$; $$$1 \le k \le 5$$$).

The array $$$[a_1, a_2, \dots, a_n]$$$ is generated as follows:

- $$$a_1$$$ is given in the input;
- for $$$2 \le i \le n$$$, $$$a_i = (a_{i-1} \cdot x + y) \bmod m$$$.

Output

Since outputting up to $$$10^7$$$ integers might be too slow, you have to do the following:

Let $$$c_i = b_i \cdot i$$$ (without taking modulo $$$998244353$$$ after the multiplication). Print the integer $$$c_1 \oplus c_2 \oplus \dots \oplus c_n$$$, where $$$\oplus$$$ denotes the bitwise XOR operator.

Example

Input

5 8 2 3 100 2

Output

1283

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2024 01:49:56 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|