#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i ) #define rep(i,n) REP(i,0,n) using ll = long long; const int inf=1e9+7; const ll longinf=1LL<<60 ; const ll mod=1e9+7 ; ll powmod(ll n,ll k, ll p){ ll ret=1; while(k){ if(k&1)ret=ret*n%p; n=n*n%p; k>>=1; } return ret; } using mat = vector>; mat mul(mat A, mat B, ll p){ mat C(2,vector(2)); rep(i,2)rep(j,2)rep(k,2){ C[i][j]+=A[i][k]*B[k][j]; } rep(i,2)rep(j,2)C[i][j]%=p; return C; } mat powmat(mat A, ll n, ll p){ mat ret(2,vector(2)); ret[0][0]=ret[1][1]=1; while(n){ if(n&1)ret=mul(ret,A,p); A = mul(A,A,p); n>>=1; } return ret; } ll calc(mat A, mat B, ll T, ll p){ ll sq = 1; while(sq*sq mp; for(int i=sq-1;i>=0;i--){ mp[powmat(A,i,p)]=i; } ll ret = longinf; rep(i,sq){ if(T-sq*i<0)break; mat g = mul(B,powmat(A,T-sq*i,p),p); if(mp.count(g))ret= min(ret,mp[g]+sq*i); } if(ret>T)return -1; return ret; } ll calc2(mat A, mat B, ll T, ll p){ ll a= A[0][0], b=A[0][1], c=A[1][0], d = A[1][1]; mat P = {{b, b}, {p-a,d}}; ll inv = powmod(b*(a+d)%p, p-2, p); mat Pi = {{d*inv%mod,(p-b)*inv%mod},{a*inv%mod, b*inv%mod}}; B = mul(P,mul(B,Pi,p),p); if(B[0][0]||B[0][1]||B[1][0])return -1; ll sq = 1; while(sq*sq mp; ll x=(a+d)%p; for(int i=sq-1;i>=0;i--){ mp[powmod(x,i,p)]=i; } ll ret = longinf; rep(i,sq){ ll g = B[1][1]*powmod(x,T-sq*i,p); if(mp.count(g))ret= min(ret,mp[g]+sq*i); } if(ret>T)return -1; return ret; } map fact(ll p, bool f){ ll tmp=p-1; mapret; for(ll i=2;i*i<=p-1;++i){ if(tmp%i==0){ while(tmp%i==0){ ret[i]++; tmp/=i; } } } if(tmp>1)ret[tmp]++; tmp = p+f; for(ll i=2;i*i<=p+1;++i){ if(tmp%i==0){ while(tmp%i==0){ ret[i]++; tmp/=i; } } } if(tmp>1)ret[tmp]++; return ret; } long long extGcd(long long a, long long b, long long &p, long long &q) { if (b == 0) { p = 1; q = 0; return a; } long long d = extGcd(b, a%b, q, p); q -= a/b * p; return d; } // 中国剰余定理 // リターン値を (r, m) とすると解は x ≡ r (mod. m) // 解なしの場合は (0, -1) をリターン pair ChineseRem(long long b1, long long m1, long long b2, long long m2) { long long p, q; long long d = extGcd(m1, m2, p, q); // p is inv of m1/d (mod. m2/d) if ((b2 - b1) % d != 0) return make_pair(0, -1); long long m = m1 * (m2/d); // lcm of (m1, m2) long long tmp = (b2 - b1) / d * p % (m2/d); long long r = (b1 + m1 * tmp)% m; if(r<0)r+=m; return make_pair(r, m); } int main(){ ll p; cin>>p; mat A(2,vector(2)), B(2,vector(2)); rep(i,2)rep(j,2)cin>>A[i][j]; rep(i,2)rep(j,2)cin>>B[i][j]; if(A==B){ cout<<1< v, r; for(auto e:fac){ if(e.second==0)continue; ll q = 1; rep(i,e.second)q*=e.first; ll res = calc(powmat(A,T/q,p),powmat(B,T/q,p),T,p); if(res==-1){ cout<<-1< ans = {0,1}; rep(i,v.size()){ ans = ChineseRem(ans.first,ans.second, r[i],v[i]); if(ans.second==-1){ cout<<-1< v, r; for(auto e:fac){ if(e.second==0)continue; ll q = 1; rep(i,e.second)q*=e.first; ll res = calc2(powmat(A,T/q,p),powmat(B,T/q,p),T,p); if(res==-1){ cout<<-1< ans = {0,1}; rep(i,v.size()){ ans = ChineseRem(ans.first,ans.second, r[i],v[i]); if(ans.second==-1){ cout<<-1< v, r; for(auto e:fac){ if(e.second==0)continue; ll q = 1; rep(i,e.second)q*=e.first; ll res = calc(powmat(A,T/q,p),powmat(B,T/q,p),T,p); if(res==-1){ cout<<-1< ans = {0,1}; rep(i,v.size()){ ans = ChineseRem(ans.first,ans.second, r[i],v[i]); if(ans.second==-1){ cout<<-1<