#include <cstdio>
using namespace std;
long long gcd(long long a, long long b) { // (a, b)
return b ? gcd(b, a % b) : a;
}
long long exGcd(long long a, long long b, long long &x, long long &y) { // ax + by = 1
if (b == ) {
x = , y = ;
return a;
}
long long d = exGcd(b, a % b, x, y);
long long t = x;
x = y;
y = t - a / b * y;
return d;
}
bool calcInv(long long a, long long p, long long &inv) { // Inv_a % p
long long x, y;
long long d = exGcd(a, p, x, y);
if ( % d == ) return inv = (x % p + p) % p, ;
else return ;
}
bool calcLinear(long long a, long long b, long long c, long long &x, long long &y) { // ax + by = c
long long _x = x, _y = y;
long long d = exGcd(a, b, _x, _y);
if (c % d) return ;
x = _x * c / d, y = _y * c / d;
return ;
}
class CRT { // x = ai mod mi
public :
bool merge(long long a, long long m, long long b, long long n, long long &r, long long &p) {
long long g = gcd(m, n);
long long c = b - a;
if (c % g) return ;
c = (c % n + n) % n;
c /= g, m /= g, n /= g;
long long inv; calcInv(m, n, inv);
c *= inv, c %= n, c *= m * g, c += a;
p = m * n * g, r = (c % p + p) % p;
return ;
}
long long calc(long long *a, long long *m, long long n) {
long long remain = a[], p = m[];
for (int i = ; i <= n; ++ i) {
long long _r, _p;
if (!merge(remain, p, a[i], m[i], _r, _p)) return -;
remain = _r, p = _p;
}
return (remain % p + p) % p;
}
} ;
template <int SIZE> class calcPrimeNumbers { // calc the prime numbers below SIZE
public :
int isNotPrime[SIZE + ];
int primes[SIZE + ];
int primeCnt;
void sieve(int lim) {
for (int i = ; i <= lim; ++ i) {
if (!isNotPrime[i]) primes[++ primeCnt] = i;
for (int j = ; j <= primeCnt && i * primes[j] <= lim; ++ j) {
isNotPrime[i * primes[j]] = ;
if (i % primes[j] == ) break ;
}
}
}
} ;
long long mul(long long a, long long b, long long p) { // a * b % p;
long long ret = ;
for (int i = ; ~ i; -- i)
ret = (ret + ret) % p, b & (1ll << i) ? ret = (ret + a) % p : ;
return ret % p;
}
long long quickPower(long long a, long long b, long long p) { // a ^ b % p
long long ret = ;
for ( ; b; b >>= , a = mul(a, a, p))
b % ? ret = mul(ret, a, p) : ;
return ret;
}
template <int SIZE> class gaussian { // gaussian elimination
public :
double mat[SIZE + ][SIZE + ];
double ans[SIZE + ];
void gauss(int n) {
static int id[SIZE + ];
for (int i = ; i <= n; ++ i) id[i] = i;
for (int i = ; i <= n; ++ i) {
int now = i;
for ( ; now <= n; ++ now) {
if (mat[id[now]][i] != ) break ;
}
if (now == n + ) continue ;
swap(id[now], id[i]);
for (int j = i + ; j <= n; ++ j) {
int ii = id[i], ij = id[j];
double t = mat[ij][i] / mat[ii][i];
for (int k = n + ; k >= i; -- k) {
mat[ij][k] = mat[ii][k] * t - mat[ij][k];
}
}
}
for (int i = n; i; -- i) {
double count = mat[id[i]][n + ];
for (int j = n; j > i; -- j) {
count -= mat[id[i]][j] * ans[j];
}
ans[i] = count / mat[id[i]][i];
}
}
} ;
template <int SIZE> class calcPhi { // calc the phi
public :
int isNotPrime[SIZE + ], primes[SIZE + ], primeCnt;
int phi[SIZE + ];
void sieve(int lim) {
phi[] = ;
for (int i = ; i <= lim; ++ i) {
if (!isNotPrime[i]) {
primes[++ primeCnt] = i;
phi[i] = i - ;
}
for (int j = ; j <= primeCnt && i * primes[j] <= lim; ++ j) {
isNotPrime[i * primes[j]] = ;
if (i % primes[j] == ) {
phi[i * primes[j]] = phi[i] * primes[j];
break ;
}
else {
phi[i * primes[j]] = phi[i] * (primes[j] - );
}
}
}
}
} ;
int main() {
return ;
}by yjl
%%%yjl