#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');
}
