Submission #405789

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll N,K;
ll f[10000];

ll mul(ll x, ll y) { return (x * y) % mod; }
ll pow(ll x, ll y) {
  ll v = 1;
  for(;y;x=mul(x,x),y>>=1)
    if(y&1) v = mul(v, x);
  return v;
}
 
ll divi(ll x, ll y) { return mul(x, pow(y, mod-2)); }


ll nCr(ll n,ll r){
  return   divi( f[n] , mul(f[n-r],f[r]));
}

ll solve(){
  if(N==K)return 1;
  if(N>K){
    return divi( f[N+K-1] , mul(f[N-1],f[K]));
  }
  K%=N;
  return nCr(N,K);
}

int main(){
  f[0]=1;
  for(int i=1;i<10000;i++)f[i]=(f[i-1]*i)%mod;

  cin>>N>>K;
  cout<<solve()<<endl;

  return 0;
}

Submission Info

Judge Result