class MathLib{
private static long safe_mod(long x, long m){
x %= m;
if(x<0) x += m;
return x;
}
private static long[] inv_gcd(long a, long b){
a = safe_mod(a, b);
if(a==0) return new long[]{b,0};
long s=b, t=a;
long m0=0, m1=1;
while(t>0){
long u = s/t;
s -= t*u;
m0 -= m1*u;
long tmp = s; s = t; t = tmp;
tmp = m0; m0 = m1; m1 = tmp;
}
if(m0<0) m0 += b/s;
return new long[]{s,m0};
}
public static long pow_mod(long x, long n, long m){
assert(n >= 0 && m >= 1);
long ans = 1;
while(n > 0){
if(n%2==1) ans = (ans * x) % m;
x = (x*x) % m;
n /= 2;
}
return ans;
}
public static long[] crt(long[] r, long[] m){
assert(r.length == m.length);
int n = r.length;
long r0=0, m0=1;
for(int i=0; i