CF690D3.The Wall (hard)

So many wall designs to choose from! Even modulo 106 + 3, it's an enormous number. Given that recently Heidi acquired an unlimited supply of bricks, her choices are endless! She really needs to do something to narrow them down.

Heidi is quick to come up with criteria for a useful wall:

• In a useful wall, at least one segment is wider than W bricks. This should give the zombies something to hit their heads against. Or,
• in a useful wall, at least one column is higher than H bricks. This provides a lookout from which zombies can be spotted at a distance.

This should rule out a fair amount of possibilities, right? Help Heidi compute the number of useless walls that do not confirm to either of these criteria. In other words, a wall is useless if every segment has width at most W and height at most H.

Parameter C, the total width of the wall, has the same meaning as in the easy version. However, note that the number of bricks is now unlimited.

Output the number of useless walls modulo 106 + 3.

有如此多的墙设计方案可供选择！即使对 $10^6 + 3$ 取模，这个数目也极其庞大。鉴于海蒂最近获得了无限供应的砖块，她的选择实际上是无穷无尽的！她确实需要采取一些措施来缩小选择范围。

海蒂很快便为“实用的墙”提出了如下判定标准：

• 在一堵实用的墙中，至少有一个段（segment）的宽度超过 $W$ 块砖。这能给僵尸提供撞头的目标；或者
• 在一堵实用的墙中，至少有一列（column）的高度超过 $H$ 块砖。这可提供一个瞭望台，便于在远处发现僵尸。

这样应该能排除掉相当多的可能性，对吧？请帮助海蒂计算不满足上述任一条件的“无用的墙”的数量。换句话说，一堵墙是无用的，当且仅当它的每个段的宽度至多为 $W$，且每列的高度至多为 $H$。

参数 $C$ 表示墙的总宽度，其含义与简单版本相同。但请注意，本题中砖块数量是无限的。

请输出无用墙的数量对 $10^6 + 3$ 取模的结果。

The first and the only line of the input contains three space-separated integers C, W and H (1 ≤ C ≤ 108, 1 ≤ W, H ≤ 100).

输入仅有一行，包含三个以空格分隔的整数 $C$、$W$ 和 $H$（$1 ≤ C ≤ 10^8$，$1 ≤ W, H ≤ 100$）。

Output the number of different walls, modulo 106 + 3, which are useless according to Heidi's criteria.

输出根据海蒂的标准判定为“无用”的不同墙体的数量，结果对 $10^6 + 3$ 取模。

If there is no brick in any of the columns, the structure is considered as a useless wall.

如果任意一列中都没有砖块，则该结构被视为无用的墙。