#include <bits/stdc++.h>
using namespace std;
int break_point() {
  char c;
  while ((c = getchar()) != '\n')
    ;
  return 0;
}
template <typename T>
void read_integer(T &r) {
  bool sign = 0;
  r = 0;
  char c;
  while (1) {
    c = getchar();
    if (c == '-') {
      sign = 1;
      break;
    }
    if (c != ' ' && c != '\n') {
      r = c - '0';
      break;
    }
  }
  while (1) {
    c = getchar();
    if (c == ' ' || c == '\n') break;
    r = r * 10 + (c - '0');
  }
  if (sign) r = -r;
}
long long binpowmod(long long a, long long b, long long mod) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res *= a;
      res %= mod;
      b--;
    } else {
      a *= a;
      a %= mod;
      b >>= 1;
    }
  }
  return res;
}
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res *= a;
      b--;
    } else {
      a *= a;
      b >>= 1;
    }
  }
  return res;
}
inline int getbit(int x, int b) { return (x >> b) & 1; }
inline long long getbit(long long x, int b) { return (x >> b) & 1; }
inline unsigned long long getbit(unsigned long long x, int b) {
  return (x >> b) & 1;
}
inline int setbit(int x, int b) { return x | (1 << b); }
inline void _setbit(int &x, int b) { x = setbit(x, b); }
inline long long setbit(long long x, int b) { return x | (1ll << b); }
inline void _setbit(long long &x, int b) { x = setbit(x, b); }
inline int unsetbit(int x, int b) { return x & (INT_MAX - (1 << b)); }
inline void _unsetbit(int &x, int b) { x = unsetbit(x, b); }
inline int countbit(int x) {
  x = x - ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  return ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
inline long long countbit(long long x) {
  int p1 = (x >> 32) & ((1ll << 32) - 1);
  int p2 = x & ((1ll << 32) - 1);
  return countbit(p1) + countbit(p2);
}
template <typename T>
void printbit(T x, int len) {
  for (int i = len - 1; i >= 0; i--) printf("%d", getbit(x, i));
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
template <typename A, typename B>
ostream &operator<<(ostream &stream, const pair<A, B> &p) {
  stream << "{" << p.first << "," << p.second << "}";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const vector<A> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A, typename B>
ostream &operator<<(ostream &stream, const map<A, B> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const set<A> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const stack<A> &v) {
  stack<A> st = v;
  stream << "[";
  while (!st.empty()) {
    stream << st.top() << " ";
    st.pop();
  }
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const priority_queue<A> &v) {
  priority_queue<A> q = v;
  stream << "[";
  while (!q.empty()) {
    stream << q.top() << " ";
    q.pop();
  }
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const queue<A> &v) {
  queue<A> q = v;
  stream << "[";
  while (!q.empty()) {
    stream << q.front() << " ";
    q.pop();
  }
  stream << "]";
  return stream;
}
void run();
int main() {
  srand(time(NULL));
  do {
    run();
    if (0) {
      0 ? printf("-------------------------------\n") : 0;
      0 ? printf("-------------------------------\n") : 0;
      0 ? break_point() : 0;
    }
  } while (0);
  return 0;
}
const int mod = 1e6 + 3;
const int N = 200005;
class Matrix {
 public:
  vector<vector<long long> > a;
  int n, m, p;
  Matrix(int _n, int _m, int _p, bool init_one = false) : n(_n), m(_m), p(_p) {
    a.resize(n);
    for (int i = 0; i < n; ++i) a[i].resize(m);
    for (int i = 0; i < n && init_one; ++i) a[i][i] = 1;
  }
  const vector<long long> &operator[](int i) const { return a[i]; }
  vector<long long> &operator[](int i) { return a[i]; }
  Matrix operator*(const Matrix &other) {
    Matrix ret(n, other.m, p);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < other.m; ++j)
        for (int k = 0; k < other.m; ++k)
          ret[i][j] = (ret[i][j] + a[i][k] * other[k][j]) % p;
    return ret;
  }
};
Matrix matrix_pow(Matrix m, int pw) {
  if (pw == 0) return Matrix(m.n, m.m, m.p, true);
  Matrix ret(m.n, m.m, m.p, true);
  while (pw) {
    if (pw & 1)
      ret = ret * m, pw--;
    else
      m = m * m, pw >>= 1;
  }
  return ret;
}
long long dp1[N];
void run() {
  int n, h, w;
  scanf("%d%d%d", &n, &w, &h);
  long long *dp = dp1 + 1;
  dp[-1] = 1;
  dp[0] = 1;
  for (int i = 1; i <= max(w - 1, 3); ++i) {
    dp[i] = dp[i - 1];
    for (int j = 1; j <= w && i - j - 1 >= -1; ++j)
      dp[i] = (dp[i] + dp[i - j - 1] * binpowmod(h, j, mod)) % mod;
  }
  if (n < max(w, 3)) {
    printf(0 ? "%lld" : "%I64d", dp[n]);
    putchar('\n');
    return;
  }
  Matrix matr(w + 1, w + 1, mod);
  for (int i = 1; i <= w; ++i) matr[i][i - 1] = 1;
  for (int i = 0; i <= w; ++i) matr[i][w] = binpowmod(h, w - i, mod);
  matr = matrix_pow(matr, n - w + 1);
  Matrix res(1, w + 1, mod);
  for (int i = 0; i <= w; ++i) res[0][i] = dp[i - 1];
  res = res * matr;
  printf(0 ? "%lld" : "%I64d", res[0][w]);
  putchar('\n');
}

### Prompt

In Cpp, your task is to solve the following problem:

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;
int break_point() {
  char c;
  while ((c = getchar()) != '\n')
    ;
  return 0;
}
template <typename T>
void read_integer(T &r) {
  bool sign = 0;
  r = 0;
  char c;
  while (1) {
    c = getchar();
    if (c == '-') {
      sign = 1;
      break;
    }
    if (c != ' ' && c != '\n') {
      r = c - '0';
      break;
    }
  }
  while (1) {
    c = getchar();
    if (c == ' ' || c == '\n') break;
    r = r * 10 + (c - '0');
  }
  if (sign) r = -r;
}
long long binpowmod(long long a, long long b, long long mod) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res *= a;
      res %= mod;
      b--;
    } else {
      a *= a;
      a %= mod;
      b >>= 1;
    }
  }
  return res;
}
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res *= a;
      b--;
    } else {
      a *= a;
      b >>= 1;
    }
  }
  return res;
}
inline int getbit(int x, int b) { return (x >> b) & 1; }
inline long long getbit(long long x, int b) { return (x >> b) & 1; }
inline unsigned long long getbit(unsigned long long x, int b) {
  return (x >> b) & 1;
}
inline int setbit(int x, int b) { return x | (1 << b); }
inline void _setbit(int &x, int b) { x = setbit(x, b); }
inline long long setbit(long long x, int b) { return x | (1ll << b); }
inline void _setbit(long long &x, int b) { x = setbit(x, b); }
inline int unsetbit(int x, int b) { return x & (INT_MAX - (1 << b)); }
inline void _unsetbit(int &x, int b) { x = unsetbit(x, b); }
inline int countbit(int x) {
  x = x - ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  return ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
inline long long countbit(long long x) {
  int p1 = (x >> 32) & ((1ll << 32) - 1);
  int p2 = x & ((1ll << 32) - 1);
  return countbit(p1) + countbit(p2);
}
template <typename T>
void printbit(T x, int len) {
  for (int i = len - 1; i >= 0; i--) printf("%d", getbit(x, i));
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
template <typename A, typename B>
ostream &operator<<(ostream &stream, const pair<A, B> &p) {
  stream << "{" << p.first << "," << p.second << "}";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const vector<A> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A, typename B>
ostream &operator<<(ostream &stream, const map<A, B> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const set<A> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const stack<A> &v) {
  stack<A> st = v;
  stream << "[";
  while (!st.empty()) {
    stream << st.top() << " ";
    st.pop();
  }
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const priority_queue<A> &v) {
  priority_queue<A> q = v;
  stream << "[";
  while (!q.empty()) {
    stream << q.top() << " ";
    q.pop();
  }
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const queue<A> &v) {
  queue<A> q = v;
  stream << "[";
  while (!q.empty()) {
    stream << q.front() << " ";
    q.pop();
  }
  stream << "]";
  return stream;
}
void run();
int main() {
  srand(time(NULL));
  do {
    run();
    if (0) {
      0 ? printf("-------------------------------\n") : 0;
      0 ? printf("-------------------------------\n") : 0;
      0 ? break_point() : 0;
    }
  } while (0);
  return 0;
}
const int mod = 1e6 + 3;
const int N = 200005;
class Matrix {
 public:
  vector<vector<long long> > a;
  int n, m, p;
  Matrix(int _n, int _m, int _p, bool init_one = false) : n(_n), m(_m), p(_p) {
    a.resize(n);
    for (int i = 0; i < n; ++i) a[i].resize(m);
    for (int i = 0; i < n && init_one; ++i) a[i][i] = 1;
  }
  const vector<long long> &operator[](int i) const { return a[i]; }
  vector<long long> &operator[](int i) { return a[i]; }
  Matrix operator*(const Matrix &other) {
    Matrix ret(n, other.m, p);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < other.m; ++j)
        for (int k = 0; k < other.m; ++k)
          ret[i][j] = (ret[i][j] + a[i][k] * other[k][j]) % p;
    return ret;
  }
};
Matrix matrix_pow(Matrix m, int pw) {
  if (pw == 0) return Matrix(m.n, m.m, m.p, true);
  Matrix ret(m.n, m.m, m.p, true);
  while (pw) {
    if (pw & 1)
      ret = ret * m, pw--;
    else
      m = m * m, pw >>= 1;
  }
  return ret;
}
long long dp1[N];
void run() {
  int n, h, w;
  scanf("%d%d%d", &n, &w, &h);
  long long *dp = dp1 + 1;
  dp[-1] = 1;
  dp[0] = 1;
  for (int i = 1; i <= max(w - 1, 3); ++i) {
    dp[i] = dp[i - 1];
    for (int j = 1; j <= w && i - j - 1 >= -1; ++j)
      dp[i] = (dp[i] + dp[i - j - 1] * binpowmod(h, j, mod)) % mod;
  }
  if (n < max(w, 3)) {
    printf(0 ? "%lld" : "%I64d", dp[n]);
    putchar('\n');
    return;
  }
  Matrix matr(w + 1, w + 1, mod);
  for (int i = 1; i <= w; ++i) matr[i][i - 1] = 1;
  for (int i = 0; i <= w; ++i) matr[i][w] = binpowmod(h, w - i, mod);
  matr = matrix_pow(matr, n - w + 1);
  Matrix res(1, w + 1, mod);
  for (int i = 0; i <= w; ++i) res[0][i] = dp[i - 1];
  res = res * matr;
  printf(0 ? "%lld" : "%I64d", res[0][w]);
  putchar('\n');
}

```