82 lines
1.6 KiB
C++
82 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
#define int long long
|
|
|
|
const int modulo = 1e9 + 7;
|
|
|
|
int k,s,t;
|
|
int fact[5000005],invfact[5000005];
|
|
|
|
int C(int x,int y)
|
|
{
|
|
if (x < y)
|
|
return 0;
|
|
if (y < 0)
|
|
return 0;
|
|
return fact[x] * invfact[y] % modulo * invfact[x - y] % modulo;
|
|
}
|
|
|
|
int f(int x,int y)
|
|
{
|
|
if (x < y)
|
|
return 0;
|
|
if (x == 0 and y == 0)
|
|
return 1;
|
|
if (y == 0)
|
|
return 0;
|
|
///in cate moduri pot distribui x in y numere pozitive
|
|
///in cate moduri pot pune y - 1 bare in x - 1 pozitii cu oricare doua bare diferite
|
|
///C(x - 1,y - 1)
|
|
return C(x - 1,y - 1);
|
|
}
|
|
|
|
int lgpow(int x,int y)
|
|
{
|
|
int z = 1;
|
|
while (y != 0)
|
|
{
|
|
if (y % 2 == 1)
|
|
z = z * x % modulo;
|
|
x = x * x % modulo;
|
|
y /= 2;
|
|
}
|
|
return z;
|
|
}
|
|
|
|
void prec()
|
|
{
|
|
fact[0] = invfact[0] = 1;
|
|
for (int i = 1; i <= 5e6; i++)
|
|
fact[i] = i * fact[i - 1] % modulo;
|
|
invfact[(int)5e6] = lgpow(fact[(int)5e6],modulo - 2);
|
|
for (int i = 5e6 - 1; i >= 1; i--)
|
|
invfact[i] = invfact[i + 1] * (i + 1) % modulo;
|
|
}
|
|
|
|
signed main()
|
|
{
|
|
prec();
|
|
cin >> k >> s >> t;
|
|
int d = k / t,r = k % t;
|
|
int ans = 0;
|
|
for (int x = 0; x <= s / (d + 1); x++)
|
|
{
|
|
if ((s - (d + 1) * x) % d == 0)
|
|
ans = (ans + f(x,r) * f((s - (d + 1) * x) / d,t - r)) % modulo;
|
|
}
|
|
cout << ans;
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
int d = k / t,r = k % t
|
|
(d + 1)(a[1] + a[2] + ... + a[r]) + d(a[r + 1] + ... + a[k])
|
|
fie x = a[1] + ... + a[r]
|
|
pentru fiecare x posibil, avem:
|
|
0 daca (s - (d + 1)x) % d != 0
|
|
f(x,r) * f((s - (d + 1)x) / d,k - r) altfel
|
|
si avem suma din asta
|
|
**/
|