subtest#1

该测试点如果使用扩展欧几里得和中国剩余定理

请注意，会爆long long

请使用龟速乘

蒟蒻的gsc：

LL gsc(LL a, LL b, LL mod){
	LL ans = 0;
	a = (a % mod + mod) % mod, b = (b % mod + mod) % mod;
	if(a < b) swap(a, b);
	while(b){
		if(b & 1) ans = (ans + a) % mod;
		a = (a + a) % mod;
		b >>= 1;
	}
	return ans;
}

验证码x4wn