// original: // https://yukicoder.me/submissions/9008 #pragma GCC optimize("Ofast") #pragma GCC target("avx2") char rbuf[256]; #define RD(v) int v=0;{int c;while(c=*rp++-48,c>=0)v=v*10+c;} #define RDL(v) long v=0;{int c;while(c=*rp++-48,c>=0)v=v*10+c;} #define MOD 1000000000 long inverse(long a, long m){ long b = m, u = 1, v = 0; while (b) { long t = a / b; long x; x=a-t*b; a=b; b=x; x=u-t*v; u=v; v=x; } return (u % m + m) % m; } int two = 0, five = 0; long rem = 1; void calc(int a, int b){ for(int i=a;i<=b;i++){ int j = i; int k=ffs(j)-1; j>>=k; two+=k; while(j % 5 == 0){ ++five; j /= 5; } rem = (rem * j) % MOD; } } main(){ read(0,rbuf,sizeof rbuf); char*rp=rbuf; RDL(n); RDL(m); n/=1000; n%=m; if(n+n>m) n=m-n; calc(1,n); rem=inverse(rem,MOD); two=-two; five=-five; calc(m-n+1,m); while(five--) rem=rem*5; printf("%ld",(rem<