#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = int(1e6) + 3;
inline int add(const int a, const int b, const int mod = MOD) {
  return (a + b >= mod) ? (a + b - mod) : (a + b);
}
inline int sub(const int a, const int b, const int mod = MOD) {
  return (a - b < 0) ? (a - b + mod) : (a - b);
}
inline void inc(int &a, const int b, const int mod = MOD) {
  a = add(a, b, mod);
}
inline int negate(const int a, const int mod = MOD) { return mod - a; }
inline int mul(const int a, const int b, const int mod = MOD) {
  return (a * 1ll * b) % mod;
}
int binPow(int b, int p, const int mod = MOD) {
  int r = 1;
  while (p) {
    if (p & 1) r = mul(r, b, mod);
    b = mul(b, b, mod);
    p >>= 1;
  }
  return r;
}
int inv(const int a, const int mod = MOD) {
  int res = binPow(a, mod - 2, mod);
  return res;
}
inline int dvd(const int a, const int b, const int mod = MOD) {
  return mul(a, inv(b, mod), mod);
}
inline int convert(int x, const int mod = MOD) {
  int tx = x % mod + mod;
  return tx > mod ? tx - mod : tx;
};
struct mNum {
  int x;
  mNum(int _x) : x(convert(_x)) {}
  mNum(long long _x) : x(convert(_x)) {}
};
mNum operator+(mNum a, mNum b) { return mNum(add(a.x, b.x)); }
mNum operator-(mNum a, mNum b) { return mNum(sub(a.x, b.x)); }
mNum operator*(mNum a, mNum b) { return mNum(mul(a.x, b.x)); }
mNum operator/(mNum a, mNum b) { return mNum(dvd(a.x, b.x)); }
mNum operator+(long long x, mNum b) { return mNum(add(convert(x), b.x)); }
mNum operator-(long long x, mNum b) { return mNum(sub(convert(x), b.x)); }
mNum operator*(long long x, mNum b) { return mNum(mul(convert(x), b.x)); }
mNum operator/(long long x, mNum b) { return mNum(dvd(convert(x), b.x)); }
mNum operator+(mNum a, long long x) { return mNum(add(a.x, convert(x))); }
mNum operator-(mNum a, long long x) { return mNum(sub(a.x, convert(x))); }
mNum operator*(mNum a, long long x) { return mNum(mul(a.x, convert(x))); }
mNum operator/(mNum a, long long x) { return mNum(dvd(a.x, convert(x))); }
const int MAX = 1e6 + 100;
int c, w, h;
int f[MAX], rf[MAX];
void precalc() {
  f[0] = 1;
  for (int i = 1; i < MAX; i++) f[i] = mul(f[i - 1], i);
  for (int i = 0; i < MAX; i++) rf[i] = inv(f[i]);
}
int C(int n, int k) {
  if (k < 0 || k > n) return 0;
  return mul(f[n], mul(rf[n - k], rf[k]));
}
void clear() {}
const int MAXP = 110;
typedef int mx[MAXP][MAXP];
typedef int row[MAXP];
void mul(mx a, mx b, mx r) {
  memset(r, 0, sizeof(mx));
  for (size_t i = 0; i < MAXP; i++)
    for (size_t j = 0; j < MAXP; j++)
      for (size_t k = 0; k < MAXP; k++)
        r[i][j] = add(r[i][j], mul(a[i][k], b[k][j]));
}
void mul(row a, mx b, row r) {
  memset(r, 0, sizeof(row));
  for (size_t j = 0; j < MAXP; j++)
    for (size_t k = 0; k < MAXP; k++) r[j] = add(r[j], mul(a[k], b[k][j]));
}
void ones(mx a) {
  memset(a, 0, sizeof(mx));
  for (size_t i = 0; i < MAXP; i++) a[i][i] = 1;
}
void binPow(mx a, int p, mx r) {
  ones(r);
  mx b;
  memcpy(b, a, sizeof(mx));
  mx t;
  while (p) {
    if (p & 1) {
      mul(r, b, t);
      memcpy(r, t, sizeof(mx));
    }
    mul(b, b, t);
    memcpy(b, t, sizeof(mx));
    p >>= 1;
  }
}
void solve() {
  int m[200] = {0};
  m[0] = 1;
  for (int i = 1; i < 200; i++) m[i] = mul(m[i - 1], h);
  int dp[MAX] = {0};
  dp[0] = 1;
  for (int n = 1; n <= c; n++) {
    for (int iw = 0; iw <= w; iw++) {
      if (n - iw - 1 < 0) continue;
      int t = mul(dp[n - iw - 1], m[iw]);
      dp[n] = add(dp[n], t);
    }
    if (n <= w) dp[n] = add(dp[n], m[n]);
  }
  printf("%d\n", dp[c]);
}
void solve1() {
  int m[MAXP] = {0};
  m[0] = 1;
  for (int i = 1; i < MAXP; i++) m[i] = mul(m[i - 1], h);
  int v[MAXP] = {0};
  v[0] = 1;
  for (int n = 1; n < MAXP; n++) {
    for (int iw = 0; iw <= w; iw++) {
      if (n - iw - 1 < 0) continue;
      int t = mul(v[n - iw - 1], m[iw]);
      v[n] = add(v[n], t);
    }
    if (n <= w) v[n] = add(v[n], m[n]);
  }
  if (c < w) {
    printf("%d\n", v[c]);
    return;
  }
  row ir;
  memcpy(ir, v, sizeof(int) * (w + 1));
  mx M;
  memset(M, 0, sizeof(M));
  for (int i = 0; i < w; i++) M[i + 1][i] = 1;
  for (int i = w; i >= 0; i--) M[i][w] = m[w - i];
  mx MP;
  binPow(M, c - w, MP);
  row rr;
  mul(ir, MP, rr);
  printf("%d\n", rr[w]);
}
int main() {
  precalc();
  while (scanf("%d%d%d", &c, &w, &h) == 3) {
    clear();
    solve1();
    return 0;
  }
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

So many wall designs to choose from! Even modulo 106 + 3, it's an enormous number. Given that recently Heidi acquired an unlimited supply of bricks, her choices are endless! She really needs to do something to narrow them down.

Heidi is quick to come up with criteria for a useful wall:

  * In a useful wall, at least one segment is wider than W bricks. This should give the zombies something to hit their heads against. Or, 
  * in a useful wall, at least one column is higher than H bricks. This provides a lookout from which zombies can be spotted at a distance. 



This should rule out a fair amount of possibilities, right? Help Heidi compute the number of useless walls that do not confirm to either of these criteria. In other words, a wall is useless if every segment has width at most W and height at most H.

Parameter C, the total width of the wall, has the same meaning as in the easy version. However, note that the number of bricks is now unlimited.

Output the number of useless walls modulo 106 + 3.

Input

The first and the only line of the input contains three space-separated integers C, W and H (1 ≤ C ≤ 108, 1 ≤ W, H ≤ 100).

Output

Output the number of different walls, modulo 106 + 3, which are useless according to Heidi's criteria.

Examples

Input

1 1 1


Output

2


Input

1 2 2


Output

3


Input

1 2 3


Output

4


Input

3 2 2


Output

19


Input

5 4 9


Output

40951


Input

40 37 65


Output

933869

Note

If there is no brick in any of the columns, the structure is considered as a useless wall.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = int(1e6) + 3;
inline int add(const int a, const int b, const int mod = MOD) {
  return (a + b >= mod) ? (a + b - mod) : (a + b);
}
inline int sub(const int a, const int b, const int mod = MOD) {
  return (a - b < 0) ? (a - b + mod) : (a - b);
}
inline void inc(int &a, const int b, const int mod = MOD) {
  a = add(a, b, mod);
}
inline int negate(const int a, const int mod = MOD) { return mod - a; }
inline int mul(const int a, const int b, const int mod = MOD) {
  return (a * 1ll * b) % mod;
}
int binPow(int b, int p, const int mod = MOD) {
  int r = 1;
  while (p) {
    if (p & 1) r = mul(r, b, mod);
    b = mul(b, b, mod);
    p >>= 1;
  }
  return r;
}
int inv(const int a, const int mod = MOD) {
  int res = binPow(a, mod - 2, mod);
  return res;
}
inline int dvd(const int a, const int b, const int mod = MOD) {
  return mul(a, inv(b, mod), mod);
}
inline int convert(int x, const int mod = MOD) {
  int tx = x % mod + mod;
  return tx > mod ? tx - mod : tx;
};
struct mNum {
  int x;
  mNum(int _x) : x(convert(_x)) {}
  mNum(long long _x) : x(convert(_x)) {}
};
mNum operator+(mNum a, mNum b) { return mNum(add(a.x, b.x)); }
mNum operator-(mNum a, mNum b) { return mNum(sub(a.x, b.x)); }
mNum operator*(mNum a, mNum b) { return mNum(mul(a.x, b.x)); }
mNum operator/(mNum a, mNum b) { return mNum(dvd(a.x, b.x)); }
mNum operator+(long long x, mNum b) { return mNum(add(convert(x), b.x)); }
mNum operator-(long long x, mNum b) { return mNum(sub(convert(x), b.x)); }
mNum operator*(long long x, mNum b) { return mNum(mul(convert(x), b.x)); }
mNum operator/(long long x, mNum b) { return mNum(dvd(convert(x), b.x)); }
mNum operator+(mNum a, long long x) { return mNum(add(a.x, convert(x))); }
mNum operator-(mNum a, long long x) { return mNum(sub(a.x, convert(x))); }
mNum operator*(mNum a, long long x) { return mNum(mul(a.x, convert(x))); }
mNum operator/(mNum a, long long x) { return mNum(dvd(a.x, convert(x))); }
const int MAX = 1e6 + 100;
int c, w, h;
int f[MAX], rf[MAX];
void precalc() {
  f[0] = 1;
  for (int i = 1; i < MAX; i++) f[i] = mul(f[i - 1], i);
  for (int i = 0; i < MAX; i++) rf[i] = inv(f[i]);
}
int C(int n, int k) {
  if (k < 0 || k > n) return 0;
  return mul(f[n], mul(rf[n - k], rf[k]));
}
void clear() {}
const int MAXP = 110;
typedef int mx[MAXP][MAXP];
typedef int row[MAXP];
void mul(mx a, mx b, mx r) {
  memset(r, 0, sizeof(mx));
  for (size_t i = 0; i < MAXP; i++)
    for (size_t j = 0; j < MAXP; j++)
      for (size_t k = 0; k < MAXP; k++)
        r[i][j] = add(r[i][j], mul(a[i][k], b[k][j]));
}
void mul(row a, mx b, row r) {
  memset(r, 0, sizeof(row));
  for (size_t j = 0; j < MAXP; j++)
    for (size_t k = 0; k < MAXP; k++) r[j] = add(r[j], mul(a[k], b[k][j]));
}
void ones(mx a) {
  memset(a, 0, sizeof(mx));
  for (size_t i = 0; i < MAXP; i++) a[i][i] = 1;
}
void binPow(mx a, int p, mx r) {
  ones(r);
  mx b;
  memcpy(b, a, sizeof(mx));
  mx t;
  while (p) {
    if (p & 1) {
      mul(r, b, t);
      memcpy(r, t, sizeof(mx));
    }
    mul(b, b, t);
    memcpy(b, t, sizeof(mx));
    p >>= 1;
  }
}
void solve() {
  int m[200] = {0};
  m[0] = 1;
  for (int i = 1; i < 200; i++) m[i] = mul(m[i - 1], h);
  int dp[MAX] = {0};
  dp[0] = 1;
  for (int n = 1; n <= c; n++) {
    for (int iw = 0; iw <= w; iw++) {
      if (n - iw - 1 < 0) continue;
      int t = mul(dp[n - iw - 1], m[iw]);
      dp[n] = add(dp[n], t);
    }
    if (n <= w) dp[n] = add(dp[n], m[n]);
  }
  printf("%d\n", dp[c]);
}
void solve1() {
  int m[MAXP] = {0};
  m[0] = 1;
  for (int i = 1; i < MAXP; i++) m[i] = mul(m[i - 1], h);
  int v[MAXP] = {0};
  v[0] = 1;
  for (int n = 1; n < MAXP; n++) {
    for (int iw = 0; iw <= w; iw++) {
      if (n - iw - 1 < 0) continue;
      int t = mul(v[n - iw - 1], m[iw]);
      v[n] = add(v[n], t);
    }
    if (n <= w) v[n] = add(v[n], m[n]);
  }
  if (c < w) {
    printf("%d\n", v[c]);
    return;
  }
  row ir;
  memcpy(ir, v, sizeof(int) * (w + 1));
  mx M;
  memset(M, 0, sizeof(M));
  for (int i = 0; i < w; i++) M[i + 1][i] = 1;
  for (int i = w; i >= 0; i--) M[i][w] = m[w - i];
  mx MP;
  binPow(M, c - w, MP);
  row rr;
  mul(ir, MP, rr);
  printf("%d\n", rr[w]);
}
int main() {
  precalc();
  while (scanf("%d%d%d", &c, &w, &h) == 3) {
    clear();
    solve1();
    return 0;
  }
  return 0;
}

```