A - Accumulation Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

うなぎはクリスマスにサンタうさぎから数列 S=\{S_1,S_2,...,S_N\} をもらいました。

うなぎは数列に含まれる数の総和を求めてみることにしました。

数列 S は、以下のような疑似コードで生成されるものです。

input N
input X,T,A,B,C
for i = 1 ... N:
  S_i = X
  for j = 1 ... T:
    X = (A*X + B) mod C

入力

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

N
X T A B C
  • 1 行目には、整数 N (1≦N≦10^6) が与えられる。
  • 2 行目には、5 つの整数 X,T,A,B,C (0≦X<C, 1≦T≦10^9, 0≦A<C, 0≦B<C, 1≦C≦10^9) が空白区切りで与えられる。

出力

数列 S に含まれる数の総和を出力せよ。 出力の末尾に改行を入れること。

入力例 1

5
5 2 3 2 1000

出力例 1

1281

数列は \{5,53,485,373,365\} となり、総和は 1281 となる。

入力例 2

1000000
868183950 1000000000 209366437 803988878 999999937

出力例 2

499932726887669