#include const unsigned long divide = 100000000; unsigned long combi(int n,int r); int main(int argc, const char * argv[]) { unsigned long N; int M; scanf("%ld",&N); scanf("%d",&M); unsigned long amari = (N - ((N/1000/M*1000) * M)) / 1000; printf("%ld\n",combi(M,(int)amari)); return 0; } unsigned long combi(int n,int r){ int i; unsigned long p=1; for (i=1;i<=r;i++){ p=p*(n-i+1)/i; if(p>= divide){ p%=divide; } } return p; }