import java.io.*; import java.util.*; class Main { public static void main(String[] args) { new Main().run(); } long MOD; long[][] pow(long[][] a, long n){ long[][] ret=new long[2][2]; ret[0][0]=ret[1][1]=1; for(;n>0;n>>=1,a=mul(a,a)){ if(n%2==1) ret=mul(ret,a); } return ret; } long[][] mul(long[][] a, long[][] b){ long[][] ret=new long[a.length][b[0].length]; for(int i=0;i0;n>>=1,a=a*a%MOD){ if(n%2==1)ret=ret*a%MOD; } return ret; } // return x s.t. a^x = b && x>0 long discretelog(long a, long b){ if(a==1){ if(b==1) return 1; else return -1; }else if(a==0){ if(b==0)return 1; else return -1; } // a^(um+v) = b // a^v = b a^(-m)^u int m=(int)Math.sqrt(MOD); long pw=1; HashMap map=new HashMap<>(); for(int v=0;v<=m;++v){ map.put(pw,v); pw=pw*a%MOD; } long ima=pow(inv(a),m); long ipw=1; for(int i=0;i<=m;++i){ if(map.containsKey(b*ipw)){ long ret=i*m+map.get(b*ipw); if(ret!=0)return ret; } ipw=ipw*ima%MOD; } return -1; } long[][] invmat(long[][] a){ if(det(a)==0)throw new AssertionError(); long[][] ret=new long[2][2]; ret[0][0]=a[1][1]; ret[1][1]=a[0][0]; ret[0][1]=(MOD-a[0][1])%MOD; ret[1][0]=(MOD-a[1][0])%MOD; for(int i=0;i<2;++i)for(int j=0;j<2;++j)ret[i][j]=ret[i][j]*inv(det(a))%MOD; return ret; } long gcd(long a,long b){ if(a>b)return gcd(b,a); if(a==0)return b; return gcd(a,b%a); } long sqrt(long a, long p) { if (a == 0) return 0; int b = 0; while (pow((b * b % p - a + p) % p, (p - 1) / 2) != p - 1) ++b; long[] d = { 1, 0 }; long[] m = { b, 1 }; long n = (p + 1) / 2; for (; n > 0; n >>= 1, m = poly_mul(m, m, b, a, p)) { if (n % 2 == 1) d = poly_mul(d, m, b, a, p); } return d[0]; } long[] poly_mul(long[] u, long[] v, long b, long a, long p) { long[] ret = new long[3]; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { ret[i + j] += u[i] * v[j]; ret[i + j] %= p; } } ret[0] += ret[2] * (b * b - a); ret[0] %= p; for (int i = 0; i < ret.length; ++i) { while (ret[i] < 0) ret[i] += p; } return Arrays.copyOf(ret, 2); } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }