Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Pratiyush Mishra
- #include <bits/stdc++.h>
- #define ll long long int
- using namespace std;
- #define mod 1000000007
- vector<ll> fact(10000, 1);
- ll power(ll x, ll n)
- {
- ll ans = 1;
- while (n != 0)
- {
- if (n % 2 == 1)
- ans = (ans * x) % mod;
- x = (x * x) % mod;
- n /= 2;
- }
- return ans % mod;
- }
- ll solve(ll n, ll m)
- {
- ll dn = power(n, mod - 2ll);
- ll dm = power(m, mod - 2ll);
- ll ans;
- ans = (fact[n + m]) % mod;
- ans = (ans * dn) % mod;
- ans = (ans * dm) % mod;
- return ans;
- }
- void mainSolve()
- {
- for (ll i = 1; i <= 1001; i++)
- fact[i] = (fact[i - 1] * i) % mod;
- ll n, m, k;
- cin >> n >> m >> k;
- ll t1(n), t2(m);
- n = max(t1, t2);
- m = min(t1, t2);
- ll ans = solve(n, m);
- if (n > k && m < k)
- {
- n = n - (k + 1) + 1;
- ll sub = solve(n, m);
- ans = (ans - sub + mod) % mod;
- }
- else if (n > k && m > k)
- {
- ll sub1 = solve(n - (k + 1) + 1, m);
- ll sub2 = solve(n, m - (k + 1) + 1);
- ll add = solve(n - (k + 1) + 1, m - (k + 1) + 1);
- ans = (ans - sub1 + mod) % mod;
- ans = (ans - sub2 + mod) % mod;
- ans = (ans + add) % mod;
- }
- cout << ans << endl;
- }
- int main()
- {
- //get(t);
- ll t = 1;
- while (t--)
- {
- mainSolve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment