Pagini recente » Cod sursa (job #1400798) | Cod sursa (job #1421735) | Cod sursa (job #1162009) | Cod sursa (job #1839960) | Cod sursa (job #464305)
Cod sursa(job #464305)
#include <cstdio>
#define ll long long
#define N 5003
#define M 2000003
int n,k;
int prod[N];
inline ll invMod(ll x)
{
ll r=1;
int aux=M-2;
for(; aux; aux>>=1)
{
if(aux&1)
r=(r*x)%M;
x=(x*x)%M;
}
return r;
}
int main()
{
freopen("sandokan.in","r",stdin);
freopen("sandokan.out","w",stdout);
scanf("%d%d",&n,&k);
if(k==2)
{
printf("1\n");
return 0;
}
k=(n-1)%(k-1);
prod[0]=prod[1]=1;
for(int i=2; i<=n; ++i)
prod[i]=((ll)prod[i-1]*(ll)i)%M;
printf("%lld\n",(((prod[n]*invMod(prod[k]))%M)*invMod(prod[n-k]))%M);
return 0;
}