#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long LL;
template<typename T>
struct RMQ
{
vector< vector<int> > rm;
T* d;
int n;
RMQ( T* d, int n ) : d(d), n(n) {
rm.push_back( vector<int>(n) );
for(int x=0; x<n; ++x)
rm[0][x] = x;
for(int k=1; (1<<k)<=n; ++k) {
rm.push_back( rm[k-1] );
for(int x=0; x+(1<<k-1)<n; ++x)
if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] )
rm[k][x] = rm[k-1][x + (1<<k-1)];
}
}
int operator()(int L, int R) const {
int k=0;
for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
LL i = rm[k][L];
LL j = rm[k][R-(1<<k)+1];
return (d[i]<=d[j] ? i : j);
}
vector<int> all(int L, int R) const {
vector<int> ans;
int minValue = d[(*this)(L, R)];
while( L <= R ) {
int C = (*this)(L, R);
if( minValue < d[C] )
break;
ans.push_back(C);
L = C+1;
}
return ans;
}
};
int B[2048][2048];
int U[2048][2048];
int D[2048][2048];
class PerfectRectangles
{
public:
int numberOfRectangles(int N, int M, int X0, int A, int _B, int Y0, int C, int _D)
{
// input
int x=X0%N, y=Y0%N;
memset(B, 0, sizeof(B));
for(int i=0; i<M; ++i) {
B[x][y] = 1;
x = (x*A+_B)%N;
y = (y*C+_D)%N;
}
// up
for(int y=0; y<N; ++y)
for(int x=0; x<N; ++x)
U[y][x] = (B[y][x] ? 0 : y==0 ? 1 : U[y-1][x]+1);
// down
for(int y=N-1; y>=0; --y)
for(int x=0; x<N; ++x)
D[y][x] = (B[y][x] ? 0 : y==N-1 ? 1 : D[y+1][x]+1);
// solve
int cnt = 0;
for(int y=0; y<N; ++y) {
RMQ<int> rmU(U[y], N);
RMQ<int> rmD(D[y], N);
stack< pair<int,int> > S;
S.push( make_pair(0, N-1) );
while( !S.empty() ) {
int L = S.top().first;
int R = S.top().second;
S.pop();
int d = rmD(L,R);
if( D[y][d] == 1 )
++cnt;
if( D[y][d] <= 1 ) {
vector<int> m = rmU.all(L, R);
m.push_back(R+1);
for(int i=0; i<m.size(); L=m[i++]+1)
if( L <= m[i]-1 )
S.push( make_pair(L, m[i]-1) );
}
}
}
return cnt;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const int &Expected, const int &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}
template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
int N = 5;
int M = 1;
int X0 = 2;
int A = 0;
int B = 0;
int Y0 = 2;
int C = 0;
int D = 0;
int RetVal = 4;
return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<1>) {
int N = 4;
int M = 4;
int X0 = 0;
int A = 1;
int B = 1;
int Y0 = 0;
int C = 1;
int D = 1;
int RetVal = 6;
return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<2>) {
int N = 1;
int M = 1000000;
int X0 = 1;
int A = 2;
int B = 3;
int Y0 = 1;
int C = 4;
int D = 7;
int RetVal = 0;
return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<3>) {
int N = 10;
int M = 20;
int X0 = 4;
int A = 76;
int B = 2;
int Y0 = 6;
int C = 2;
int D = 43;
int RetVal = 12;
return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<4>) {
int N = 1999;
int M = 4000000;
int X0 = 1000;
int A = 1;
int B = 1;
int Y0 = 0;
int C = 1;
int D = 1;
int RetVal = 1002995;
return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<5>) {
int N = 2000;
int M = 4000000;
int X0 = 1500;
int A = 1;
int B = 1;
int Y0 = 500;
int C = 1;
int D = 1;
int RetVal = 1003997;
return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<> void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE