Cod sursa(job #210685)
Utilizator | Florea Mihai Alexandru mihai_florea | Data | 28 septembrie 2008 17:17:08 |
---|---|---|---|
Problema | Sandokan | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.6 kb |
#include <stdio.h>
#define P 2000003
int N,K;
int Pow(int a,int b){
long long x=1,y=a;
while(b > 0){
if(b%2 == 1) x=(x*y)%P;
y = (y*y)%P;
b /= 2;
}
return x%P;
}
int main(){
int i,sol=1,r,inv;
freopen("sandokan.in","r",stdin);
freopen("sandokan.out","w",stdout);
scanf("%d %d",&N,&K);
for (r=N;r>=K;) r-=(K-1);
N--;K=r-1;
for (i=r=1;i<=K;++i){
r=(long long)r*i%P;
sol=(long long)sol*(N-K+i)%P;
}
inv=Pow(r,P-2);
sol=(long long)sol*inv%P;
printf("%d",sol);
return 0;
}