#include <bits/stdc++.h>
using namespace std;
template <class T>
T min(T a, T b, T c) {
  return min(a, min(b, c));
}
template <class T>
T max(T a, T b, T c) {
  return max(a, max(b, c));
}
struct matrix {
  vector<vector<long long> > a;
  int m, n;
  matrix(int _m, int _n) {
    m = _m;
    n = _n;
    a.resize(m + 1);
    for (int i = (1); i <= (m); ++i) a[i].resize(n + 1);
  }
  void read() {
    for (int i = (1); i <= (m); ++i) {
      for (int j = (1); j <= (n); ++j) scanf("%lld", &a[i][j]);
    }
  }
  bool inline operator==(const matrix &o) const {
    if (m != o.m || n != o.n) return false;
    for (int i = (1); i <= (m); ++i) {
      for (int j = (1); j <= (n); ++j) {
        if (a[i][j] != o.a[i][j]) return false;
      }
    }
    return true;
  }
  void inline operator=(const matrix &o) {
    m = o.m;
    n = o.n;
    for (int i = (1); i <= (m); ++i) {
      for (int j = (1); j <= (n); ++j) a[i][j] = o.a[i][j];
    }
  }
  matrix inline operator*(const matrix &o) const {
    matrix c(m, o.n);
    for (int i = (1); i <= (m); ++i) {
      for (int j = (1); j <= (o.n); ++j) {
        c.a[i][j] = 0;
        for (int k = (1); k <= (n); ++k)
          c.a[i][j] = (c.a[i][j] + a[i][k] * o.a[k][j]) % 1000003;
      }
    }
    return c;
  }
  void print() {
    for (int i = (1); i <= (m); ++i) {
      for (int j = (1); j <= (n); ++j) printf("%lld ", a[i][j]);
      puts("");
    }
    puts("");
  }
};
matrix matPow(matrix A, int n) {
  if (n == 1) return A;
  if (n % 2 == 1) return A * matPow(A, n - 1);
  matrix B = matPow(A, n / 2);
  return B * B;
}
int n, H, W;
int main() {
  scanf("%d%d%d", &n, &W, &H);
  n += 1;
  matrix A(W + 1, W + 1);
  for (int i = (1); i <= (W); ++i) A.a[i][i + 1] = 1;
  A.a[W + 1][W + 1] = 1;
  for (int j = (W); j >= (1); --j)
    A.a[W + 1][j] = (A.a[W + 1][j + 1] * H) % 1000003;
  matrix F(W + 1, 1);
  F.a[1][1] = 1;
  for (int i = (2); i <= (W + 1); ++i) {
    int p = 1;
    for (int j = (i - 1); j >= (1); --j) {
      F.a[i][1] = (F.a[i][1] + F.a[j][1] * p) % 1000003;
      p = (p * H) % 1000003;
    }
  }
  if (n <= W)
    cout << F.a[n + 1][1];
  else
    cout << (matPow(A, n - W) * F).a[W + 1][1];
  return 0;
}
