#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int MOD = 1e6 + 3;
const int N = 1e2 + 5;
int n, wid, hei;
long long f[N], phei[N];
struct matrix {
  long long a[N][N];
  matrix() { memset(a, 0, sizeof(a)); }
} base, cur;
matrix operator*(matrix a, matrix b) {
  matrix ans;
  for (auto i = (0); i <= (wid); i++)
    for (auto j = (0); j <= (wid); j++)
      for (auto k = (0); k <= (wid); k++)
        ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j]) % MOD;
  return ans;
}
void prepare() {
  cin >> n >> wid >> hei;
  phei[0] = 1;
  for (auto i = (1); i <= (wid); i++) phei[i] = phei[i - 1] * hei % MOD;
  f[0] = 1;
  for (auto i = (1); i <= (wid); i++)
    for (int j = 1; j <= min(i, wid); j++)
      f[i] = (f[i] + f[i - j] * phei[j - 1]) % MOD;
  for (auto i = (1); i <= (wid); i++) base.a[i][i - 1] = 1;
  for (auto i = (0); i <= (wid); i++) base.a[i][wid] = phei[wid - i];
}
long long solve() {
  n++;
  if (n <= wid) return f[n];
  n -= wid;
  for (auto i = (0); i <= (wid); i++) cur.a[i][i] = 1;
  while (n) {
    if (n & 1) cur = cur * base;
    base = base * base;
    n >>= 1;
  }
  long long ans = 0;
  for (auto i = (0); i <= (wid); i++) ans = (ans + f[i] * cur.a[i][wid]) % MOD;
  return ans;
}
int main() {
  prepare();
  cout << solve();
}
