ホームに戻る
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;
}

inserted by FC2 system