pratiyush7

Untitled

Dec 4th, 2021
849
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Pratiyush Mishra
  2.  
  3.  
  4. #include <bits/stdc++.h>
  5. #define ll long long int
  6. using namespace std;
  7. #define mod 1000000007
  8. vector<ll> fact(10000, 1);
  9.  
  10. ll power(ll x, ll n)
  11. {
  12.     ll ans = 1;
  13.     while (n != 0)
  14.     {
  15.         if (n % 2 == 1)
  16.             ans = (ans * x) % mod;
  17.         x = (x * x) % mod;
  18.         n /= 2;
  19.     }
  20.     return ans % mod;
  21. }
  22.  
  23. ll solve(ll n, ll m)
  24. {
  25.     ll dn = power(n, mod - 2ll);
  26.     ll dm = power(m, mod - 2ll);
  27.     ll ans;
  28.     ans = (fact[n + m]) % mod;
  29.     ans = (ans * dn) % mod;
  30.     ans = (ans * dm) % mod;
  31.     return ans;
  32. }
  33.  
  34. void mainSolve()
  35. {
  36.     for (ll i = 1; i <= 1001; i++)
  37.         fact[i] = (fact[i - 1] * i) % mod;
  38.     ll n, m, k;
  39.     cin >> n >> m >> k;
  40.     ll t1(n), t2(m);
  41.     n = max(t1, t2);
  42.     m = min(t1, t2);
  43.     ll ans = solve(n, m);
  44.     if (n > k && m < k)
  45.     {
  46.         n = n - (k + 1) + 1;
  47.         ll sub = solve(n, m);
  48.         ans = (ans - sub + mod) % mod;
  49.     }
  50.     else if (n > k && m > k)
  51.     {
  52.         ll sub1 = solve(n - (k + 1) + 1, m);
  53.         ll sub2 = solve(n, m - (k + 1) + 1);
  54.         ll add = solve(n - (k + 1) + 1, m - (k + 1) + 1);
  55.         ans = (ans - sub1 + mod) % mod;
  56.         ans = (ans - sub2  + mod) % mod;
  57.         ans = (ans + add) % mod;
  58.     }
  59.     cout << ans << endl;
  60. }
  61.  
  62. int main()
  63. {
  64.     //get(t);
  65.     ll t = 1;
  66.     while (t--)
  67.     {
  68.         mainSolve();
  69.     }
  70.     return 0;
  71. }
  72.  
RAW Paste Data