long i;a['00']['00'],m=1e9,j;main(){for(**a=1;i+j--?a[i][-j]=(a[i-1][-j]+a[i-1][~j])%m,1:(j=i++<1e4||!printf("%d",a[j][i/1000%j],scanf("%ld%d",&i,&j))););}