E: Expensive Function

問題文

数列$a$と非負整数上の関数$f(x)$が以下のように定義されています。

• $a_1 = 0$
• $a_i = (a_{i-1} \times p + q) \bmod M (i \geq2)$
• $f(x) = x \mbox{ XOR } a_1 \mbox{ XOR } a_2 \mbox{ XOR } ... \mbox{ XOR } a_{10^8}$

松崎くんが計算すると、$f(s) = t$ でした。 非負整数 $y$ が与えられるので、$f(y)$ を求めてください。

$n$ 個の非負整数 $x_1, x_2, \ldots, x_n$ の排他的論理和 $x_1 \mbox{ XOR } x_2 \mbox{ XOR } \ldots \mbox{ XOR } x_n$ は以下のように定義されます:

• $x_1 \mbox{ XOR } x_2 \mbox{ XOR } \ldots \mbox{ XOR } x_n$ を二進表記した際の $2^k ( k \geq 0 )$ の位の数は $x_1, x_2, \ldots, x_n$ のうち、二進表記した際の $2^k ( k \geq 0 )$ の位の数が $1$ となるものの個数が奇数ならば $1$ 、そうでなければ $0$ となる。

制約

• $0 \leq p, q, s, t, y \leq 10^9$
• $1 \leq M \leq 10^9$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

$s$  $t$
$p$ $q$ $M$
$y$

出力

$f(y)$ を出力してください。

入出力例

入力例1

0 15656
3 7 13333
0

出力例1

15656

入力例2

0 0
0 0 3
0

出力例2

0

入力例3

1000000000 1000000000
1000000000 1000000000 1000000000
1000000000

出力例3

1000000000

---