板板们

inline int exgcd (const int &a, const int &b, int &x, int &y) {
	if (!b) return x = 1, y = 0, a;
	int d = exgcd(b, a % b, y, x);
	return y -= a / b * x, d;
}
inline int inv (const int &a, const int &m) {
	int x, y, d = exgcd(a, m, x, y);
	return (x % m + m) % m;
}
inline int CRT (const int *a, const int *m) {
	int M = 1, res = 0;
	for (int i = 1; i <= n; i++) M *= m[i];
	for (int i = 1; i <= n; i++) {
		int Mi = M / m[i];
		(res += a[i] * Mi * inv(Mi, m[i])) %= M;
	}
	return res < 0 ? res + M : res;
}