#include using namespace std; #define int long long #define rep(i,s,n) for(int i = s;i=(s);i--) #define all(v) (v).begin(),(v).end() #define pb push_back #define fi first #define se second #define chmin(a,b) a=min((a),(b)) #define chmax(a,b) a=max((a),(b)) typedef long long ll; typedef pairpint; typedef vectorvint; typedef vectorvpint; typedef pair P1; typedef pair P2; typedef pairPP; static const ll maxLL = (ll)1 << 62; const ll MOD=1000000007; const ll INF=1e18; int dx[]={0,0,1,-1}; int dy[]={-1,1,0,0}; int N,M; int mod=1e9; int a[10010][10010]; signed main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>N>>M; N%=1000*M; N/=1000; rep(i,0,10001)rep(j,0,i+1){ if(j==0)a[i][j]=1; else a[i][j]=(a[i-1][j]+a[i-1][j-1])%mod; } cout<