fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using ld = long double;
  5.  
  6. #define int ll
  7. #define endl '\n'
  8. #define all(v) (v).begin(), (v).end()
  9. #define rall(v) (v).rbegin(), (v).rend()
  10. #define Ragaey ios::sync_with_stdio(false), cin.tie(nullptr)
  11.  
  12. ll MOD = 1e9 + 7;
  13.  
  14. ll mult(ll a, ll b) { return ((a % MOD) * (b % MOD)) % MOD; }
  15.  
  16. ll fp(ll base, ll power) {
  17.   if (power == 0)
  18.     return 1;
  19.  
  20.   ll hp = fp(base, power / 2);
  21.   ll fullPower = mult(hp, hp);
  22.  
  23.   if (power % 2)
  24.     fullPower = mult(fullPower, base);
  25.  
  26.   return fullPower;
  27. }
  28.  
  29. ll divi(ll a, ll b) { return mult(a, fp(b, MOD - 2)); }
  30.  
  31. void solve() {
  32.   int n, k, d;
  33.   cin >> n >> k >> d;
  34.  
  35.   if (n - (k - 1) * d + k < 2 * k) {
  36.     cout << 0 << endl;
  37.     return;
  38.   }
  39.  
  40.   int ans = 1;
  41.   for (int i = 0; i < 2 * k; i++)
  42.     ans = mult(ans, n - (k - 1) * d + k - i);
  43.  
  44.   int fact = 1;
  45.   for (int i = 1; i <= 2 * k; i++)
  46.     fact = mult(fact, i);
  47.  
  48.   ans = divi(ans, fact);
  49.   cout << ans << endl;
  50. }
  51.  
  52. signed main() {
  53.   Ragaey;
  54.  
  55.   int tc = 1;
  56.   // cin >> tc;
  57.   while (tc--)
  58.     solve();
  59. }
  60.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
4 2 1
stdout
copy 
5
https://ideone.com/Rn0QIk
language:
C++ (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!