Submission #2516607

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <iomanip>
#include <queue>
#include <map>
#include <set>
#include <random>
#include <sstream>
#include <stack>
#include <deque>

using namespace std;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

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

const int mod = (int) 1e9 + 7;

long long madd(long long a, long long b) {
    return (a + b) % mod;
}

long long msub(long long a, long long b) {
    return (a + mod - b) % mod;
}

long long mmul(long long a, long long b) {
    return ((a % mod) * (b % mod)) % mod;
}

long long mpow(long long a, long long b) {
    long long ans = 1;
    long long k = a;
    while (b > 0) {
        if (b % 2 == 0) {
            b /= 2;
            k = mmul(k, k);
        } else {
            b -= 1;
            ans = mmul(ans, k);
        }
    }
    return ans;
}

long long mdiv(long long a, long long b) {
    return mmul(a, mpow(b, mod-2));
}

ll combi(ll n, ll r) {
    ll a = 1;
    ll b = 1;
    rep(i,r) a = mmul(a, n-i);
    rep(i,r) b = mmul(b, r-i);
    return mdiv(a, b);
}

int N, K;

int main() {
    cin >> N >> K;
    if (K / N == 0) {
        cout << combi(N + K - 1, K) << endl;
    } else {
        cout << combi(N, K % N) << endl;
    }
    return 0;
}

Submission Info

Judge Result