Submission #405803

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;

const int INF = 1e9;
const int MOD = 1e9+7;

class modComb{
    private:
        const ll MAX_N, M;
        vector<ll> fact, invfact;

        ll extgcd(ll a, ll b, ll &x, ll &y){
            ll g = a; x = 1; y = 0;
            if(b) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
            return g;
        }

        ll invMod(ll a){
            ll x, y;
            if(extgcd(a, M, x, y) == 1) return (x + M) % M;
            else return 0;
        }
    public:
        modComb(const ll n, const ll mod) : MAX_N(n), M(mod){
            fact.resize(MAX_N, 1);
            for(int i = 2; i < MAX_N; i++)
                fact[i] = (fact[i-1] * i) % M;
            invfact.resize(MAX_N, 1);
            invfact[MAX_N-1] = invMod(fact[MAX_N-1]);
            for(int i = MAX_N-2; i >= 1; i--)
                invfact[i] = (invfact[i+1] * (i+1)) % M;
        }

        ll operator()(const ll n, const ll r){
            if(n < 0 || r < 0 || n < r) return 0;
            return (((fact[n] * invfact[n-r]) % M) * invfact[r]) % M;
        }
};


int main(void){
    ll N, K;
    cin >> N >> K;	
    ll a = K / N;
    ll b = K - a * N;
    if(a == 0){
        modComb nCr(N + K + 2, MOD);
        cout << nCr(N + K - 1, N - 1) << endl;
        return 0;   
    }
    modComb nCr(N + 1, MOD);
    cout << nCr(N, b) << endl;
    return 0;
}

Submission Info

Judge Result