Sam was staying up late one night, trying to analyze her research data. Unfortunately, in her sleep-deprived state, she forgot to save her work and it was eaten by some fast-moving cobras! Luckily, she remembers that she had generated her ~n~ points of data using a Linear Congruence Generator parameterized by three values, ~a, b~, and ~m~. For her analysis she needs to find the bitwise-xor of all of her data points, and she has turned to you to recover her data. Help her analyze her data quickly before her thesis is due!

For precise details on how the generator works, read the pseudocode below.

Generator Pseudocode

x = 0
for i in range(n):
    x *= a
    x += b
    x %= m

    data[i] = x

Input Format

The only line of input consists of four integers: ~n, a, b, m~.

Output Format

Output a single integer: the bitwise-xor of all the data values.

Constraints

~1 \leq n \leq 3 \times 10^8~

~1 \leq a, b, m \leq 10^9~

Sample Input

1000 6 1 65536

Sample Output

22478