Cerința

Se dau numerele naturale n, x, y, z, t. Se generează vectorul a astfel: a[i] = (a[i-1] * x + y) % z, pentru 1 ≤ i ≤ n si a[i] = 0 pentru i = 0. Determinați ∑(a[i] XOR a[j]), unde 1 ≤ i < j ≤ n, modulo t.

Date de intrare

Programul citește de la tastatură numerele n, x, y, z, t.

Date de ieșire

Programul va afișa pe ecran numărul cerut.

Restricții și precizări

• 1 ≤ n ≤ 250.000
• 1 ≤ x, y, z, t < 2^62

Exemplu:

Intrare

3 1 1 4 7

Ieșire

6

Explicație

a = {0, 1, 2, 3}
S = ((1 XOR 2) + (1 XOR 3) + (2 XOR 3)) MOD 7 = (3 + 2 + 1) MOD 7 = 6