#define ll long longll inv(int a, int p) { // 求逆元 /* int x, y, d; exgcd(a, p, d, x, y); if(d == 1) return (x%p+p)%p; */ /* return qp(a, p-2, p); */ return -1;}ll CRT(ll *a, int *m) { ll M = 1, res = 0; for(int i = 1; i <= *m; i ++ ) M *= m[i]; for(int i = 1; i <= *m; i ++ ) { ll tmp = M/m[i]; res = (res+tmp*inv(tmp, m[i])%M*a[i])%M; } return (res+M)%M;}