//---------------------------------------------------------------------------
#pragma option -Od
//---------------------------------------------------------------------------
#include <stdio.h>
//---------------------------------------------------------------------------
#define MAX_M 7000
//---------------------------------------------------------------------------
int T0, T1, a, b, x, y, z, M;
long long n;
int cache0[MAX_M]; //=a * T(n-2)^^2 + x * T(n-2) ; for each T(n-2)
int cache1[MAX_M]; //=b * T(n-1)^^2 + y * T(n-1) + z ; for each T(n-1)
//---------------------------------------------------------------------------
void init()
{
FILE *F= fopen("rsir.in", "rt");
fscanf(F, "%d %d %d %d %d %d %d %d %Ld",
&T0, &T1, &a, &b, &x, &y, &z, &M, &n);
fclose(F);
T0%= M;
T1%= M;
for (int I= M; --I>= 0; ) {
int sqr= I* I % M;
cache0[I]= (a* sqr+ x* I ) % M;
cache1[I]= (b* sqr+ y* I+ z) % M;
}
}
//---------------------------------------------------------------------------
#define NEXT1(lo, hi) \
{ \
int sav= hi; \
hi= cache0[lo]+ cache1[hi]; \
if (hi>= M) hi-= M; \
lo= sav; \
} //one iteration...
//---------------------------------------------------------------------------
#define NEXT2(lo, hi) \
{ \
lo= cache0[lo]+ cache1[hi]; \
if (lo>= M) lo-= M; \
hi= cache0[hi]+ cache1[lo]; \
if (hi>= M) hi-= M; \
} //two iterations...
//---------------------------------------------------------------------------
int calc()
{
int p0, p1, q0, q1;
p0= q0= T0;
p1= q1= T1;
int index= 0; //index of (p0, p1)
do {
NEXT1(p0, p1);
index++;
NEXT2(q0, q1);
} while (p0!= q0 || p1!= q1);
int s0= p0, s1= p1;
//acum perechea (p0, p1) face parte din ciclu, la index-ul index;
//aplicam acelasi algoritm pentru a afla lungimea ciclului...
int cycle= 0;
do {
NEXT1(p0, p1);
cycle++;
NEXT2(q0, q1);
} while (p0!= q0 || p1!= q1);
n= (n- index) % cycle + index; //n se reduce la un singur ciclu...
int r0= T0, r1= T1;
if (n>= index) {
n-= index;
r0= s0;
r1= s1; //evita primele calcule...
}
for (int I= ((int)n)>> 1; --I>= 0; )
NEXT2(r0, r1);
if (((int)n) & 1)
return r1;
return r0;
}
//---------------------------------------------------------------------------
void outp()
{
FILE *G= fopen("rsir.out", "wt");
fprintf(G, "%d\n", calc());
fclose(G);
}
//---------------------------------------------------------------------------
int invert(int A, int M)
{
int max= M,
inv= 0;
for (int I= 1; I< M; I++)
if (A* I % M< max) {
inv= I;
max= A* I % M;
}
return inv;
}
//---------------------------------------------------------------------------
void test()
{
//test if a*x^2+ b*x can be written as a(x+b/2a)^2- b*b/4a
int M= 2000;
int A= 20;
int inv = invert(A , M),
inv2= invert(A* 2, M),
inv4= invert(A* 4, M);
for (int B= M; --B>= 0; )
for (int X= M; --X>= 0; ) {
int T= (A* X* X+ B* X) % M;
int Q= (X+ B* inv2) % M;
int S= (A* Q* Q- B* B* inv4) % M;
if (S< 0)
S+= M;
S= S* 4* A % M;
T= T* 4* A % M;
if (S!= T)
printf("err");
}
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
// test();
init();
outp();
return 0;
}
//---------------------------------------------------------------------------
/*
Rsir
Construim un sir recurent astfel:
Tn = a * T(n-2)^^2 + b * T(n-1)^^2 + x * T(n-2) + y * T(n-1) + z
Cerinta
Fiind date T0, T1, a, b, x, y, z si n calculati Tn modulo un numar natural M.
Date de intrare
Fisierul de intrare rsir.in contine pe prima linie numerele naturale T0, T1, a, b, x, y, z, M si n, separate prin spatiu, cu semnificatia din enunt.
Date de iesire
Fisierul de iesire rsir.out va contine o singura linie pe care va fi scris un numar natural reprezentand Tn modulo M.
Restrictii
0 <= a, b, x, y, z <= 1.000
0 <= T0, T1 <= 1.000.000.000
0 <= n <= 1016
1 <= M <= 7.000
Exemplursir.in rsir.out
1 1 0 0 1 1 0 1000 7 21
Explicatie
Termenii sirului sunt:
T0=1
T1=1
T2=0*12+0*12+1*1+1*1+0=2
T3=0*12+0*22+1*1+1*2+0=3
T4=0*22+0*32+1*2+1*3+0=5
T5=0*32+0*52+1*3+1*5+0=8
T6=0*52+0*82+1*5+1*8+0=13
T7=0*82+0*132+1*8+1*13+0=21
Rezultatul este T7 mod 1000 = 21.
*/
//---------------------------------------------------------------------------