1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define _for(i,a,b) for(int i = (a);i < b;i ++) 5 typedef long long ll; 6 using namespace std; 7 int a[1000003]; 8 inline ll read() 9 { 10 ll ans = 0; 11 char ch = getchar(), last = ' '; 12 while(!isdigit(ch)) last = ch, ch = getchar(); 13 while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); 14 if(last == '-') ans = -ans; 15 return ans; 16 } 17 inline void write(ll x) 18 { 19 if(x < 0) x = -x, putchar('-'); 20 if(x >= 10) write(x / 10); 21 putchar(x % 10 + '0'); 22 } 23 24 int main() 25 { 26 int N = read(); 27 int K = read(); 28 memset(a,0,sizeof(a)); 29 a[0] = 1; 30 a[1] = 1; 31 _for(i,2,N+1) 32 { 33 _for(j,1,K+1) 34 { 35 if(i-j<0) 36 break; 37 a[i] += a[i-j]; 38 a[i] %= 100003; 39 } 40 } 41 write(a[N]); 42 return 0; 43 }