#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
const long long mod = 1e6 + 3;
const int INF = 1e9 + 1;
const int N = 105;
long long H[N], c, h, w;
struct Matrix {
  long long arr[N][N];
  Matrix() { memset(arr, 0, sizeof arr); }
  Matrix(int x) {
    memset(arr, 0, sizeof arr);
    for (int i = 0; i < w + 1; i++) arr[i][i] = x;
  }
  Matrix operator*(Matrix a) {
    Matrix ret;
    for (int i = 0; i < w + 1; i++) {
      for (int j = 0; j < w + 1; j++) {
        for (int k = 0; k < w + 1; k++) {
          ret.arr[i][j] += this->arr[i][k] * a.arr[k][j];
          ret.arr[i][j] %= mod;
        }
      }
    }
    return ret;
  }
};
Matrix poww(Matrix a, int p) {
  if (!p) return Matrix(1);
  Matrix ret = poww(a, p >> 1);
  ret = ret * ret;
  if (p & 1) ret = ret * a;
  return ret;
}
void print(Matrix a) {
  for (int i = 0; i < w + 1; i++) {
    for (int j = 0; j < w + 1; j++) {
      cout << a.arr[i][j] << " ";
    }
    cout << "\n";
  }
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  H[0] = 1;
  cin >> c >> w >> h;
  for (int i = 1; i < N; i++) H[i] = (H[i - 1] * h) % mod;
  Matrix A = Matrix(), B = Matrix();
  for (int i = 0; i < w + 1; i++) {
    B.arr[i][0] = H[i];
  }
  for (int i = 0; i < w; i++) {
    B.arr[i][i + 1] = 1;
  }
  A.arr[0][0] = A.arr[0][1] = 1;
  B = poww(B, c + 1);
  cout << B.arr[0][0];
}
