CF690D3 The Wall (hard)

有太多的墙体设计可以选择了！即使对 $10^{6}+3$ 取模，这个数字依然非常庞大。最近 Heidi 获得了无限量的砖块，她的选择变得无穷无尽！她真的需要一些方法来缩小选择范围。 Heidi 很快就想出了一个有用墙体的标准： - 在一个有用的墙体中，至少有一段的宽度大于 $W$ 块砖。这能让僵尸撞到头。或者， - 在一个有用的墙体中，至少有一列的高度大于 $H$ 块砖。这可以作为瞭望台，从远处发现僵尸。 这样应该能排除不少可能性吧？请你帮 Heidi 计算不符合上述任一标准的无用墙体的数量。换句话说，如果每一段的宽度都不超过 $W$，且每一列的高度都不超过 $H$，那么这个墙体就是无用的。 参数 $C$ 表示墙体的总宽度，与简单版本中的含义相同。但请注意，现在砖块的数量是无限的。 请输出无用墙体的数量，对 $10^{6}+3$ 取模。

输入仅一行，包含三个用空格分隔的整数 $C$、$W$ 和 $H$，满足 $1 \leq C \leq 10^{8}$，$1 \leq W,H \leq 100$。

输出一个整数，表示无用墙体的不同方案数，对 $10^{6}+3$ 取模。

如果所有列都没有砖块，这种结构也被视为无用墙体。 由 ChatGPT 4.1 翻译