Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define MOD 1000000007
  4. using namespace std;
  5.  
  6. ll mod(ll a, ll b) {
  7.     return (b + a%b) % b;
  8. }
  9.  
  10. ll exgcd(ll a, ll b, ll &x, ll &y) {
  11.     if(a == 0) {
  12.         x = 0, y = 1;
  13.         return b;
  14.     }
  15.     ll xx, yy, g;
  16.     g = exgcd(b%a, a, xx, yy);
  17.     x = yy - xx*(b/a);
  18.     y = xx;
  19.     return g;
  20. }
  21.  
  22. ll fact(ll N) {
  23.     if (N == 0)
  24.         return 1;
  25.     else
  26.         return ((N % MOD) * (fact(N - 1) % MOD)) % MOD;
  27. }
  28.  
  29. int cnk(int n, int k) {
  30.     ll a, b;
  31.     exgcd(((fact(k) % MOD)* (fact(n - k) % MOD)) % MOD, MOD, a, b);
  32.     return mod(fact(n) * a, MOD);
  33. }
  34.  
  35. int main()
  36. {
  37.     int n, m;
  38.     cin >> n >> m;
  39.     cout << cnk(n + m, n) % MOD;
  40.     return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement