func_code_string: #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();   }   