Advertisement
Guest User

Untitled

a guest
Apr 5th, 2020
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const ll mod = 1e9 + 7;
  6.  
  7. ll mul(ll a, ll b){
  8.     if(!(b ^ 0ll))
  9.         return 0;
  10.     ll t = mul(a, b >> 1) % mod;
  11.     if(b & 1ll)
  12.         return ( (t << 1) % mod + (a % mod) ) % mod;
  13.     return (t << 1) % mod;
  14. }
  15.  
  16. ll reverse_modulo(ll v){
  17.     ll a = v, b = mod, r, q;
  18.     ll xa = 1, xb = 0, xr;
  19.     while(b != 0){
  20.         q = a / b;
  21.         r = a - q * b;
  22.         xr = xa - q * xb;
  23.         a = b;
  24.         xa = xb;
  25.         b = r;
  26.         xb = xr;
  27.     }
  28.     return (xa + mod) % mod;
  29. }
  30.  
  31. int main()
  32. {
  33.     ll n, k;
  34.     cin >> n >> k;
  35.     if(k > ((n + 1) >> 1))
  36.         cout << '0';
  37.     else{
  38.         ll ans = 1, gt = 1;
  39.         for(ll i = 0; i < k; ++i){
  40.             ans = mul(ans, n - ((k - 1ll) << 1) + i);
  41.             gt = gt * (i + 1ll) % mod;
  42.         }
  43.         ans = mul(ans, reverse_modulo(gt));
  44.         cout << ans;
  45.     }
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement