# 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