ホームに戻る
1000000007の計算
long long add(long long x, long long y){
if(x >= MOD){
x %= MOD;
}
if(y >= MOD){
y %= MOD;
}
x += y;
if(x >= MOD){
x -= MOD;
}
return x;
}
long long mul(long long x, long long y){
if(x >= MOD){
x %= MOD;
}
if(y >= MOD){
y %= MOD;
}
x *= y;
if(x >= MOD){
x %= MOD;
}
return x;
}
long long modpow(long long a, long long b){
long long r = 1LL;
while(b){
if(b & 1LL)r *= a;
if(r >= MOD)r %= MOD;
a *= a;
if(a >= MOD)a %= MOD;
b >>= 1LL;
}
return r;
}
// n! は nPn で実装できます。
long long nPr(long long n, long long r){
long long ret = 1LL;
for(int i = 1; i <= r; ++i){
ret = (ret * ((n - i + 1) % MOD)) % MOD;
}
return ret;
}
// 中で modpow を使っています。
long long nCr(long long n, long long r){
long long ret = 1LL;
for(int i = 1; i <= r; ++i){
ret = (ret * ((n - i + 1) % MOD)) % MOD;
}
for(int i = 1; i <= r; ++i){
ret = (ret * modpow(i, MOD - 2)) % MOD;
}
return ret;
}
// O(nlogn)で準備、O(1)でnCrを計算する。
// 内部でmodpowを使用します。
#define N_MAX 2001
long long fact[N_MAX];
long long rfact[N_MAX];
long long nCr(long long n, long long r){
long long ret = 1LL;
ret *= fact[n];
ret %= MOD;
ret *= rfact[r];
ret %= MOD;
ret *= rfact[n-r];
ret %= MOD;
return ret;
}
clr(fact,0);
fact[0]=1;
rep(i,1,N_MAX){
fact[i] = fact[i-1]*i;
fact[i] %= MOD;
}
clr(rfact,0);
rfact[0]=1;
rep(i,1,N_MAX){
rfact[i] = rfact[i-1]*modpow(i,MOD-2);
rfact[i] %= MOD;
}