← 返回题目列表

Codeforces · 690/D3

D3. 墙(硬)

中文机器翻译题面 查看原题

如此多的墙壁设计可供选择!即使对 106 + 3 求模,这也是一个巨大的数字。鉴于海蒂最近获得了无限量的积木,她的选择是无穷无尽的!她确实需要做点什么来缩小范围。

海蒂很快就提出了有用的墙的标准:

- 在一堵有用的墙中,至少有一段比 W 砖宽。这应该会给僵尸一些可以撞到的东西。或者,
- 在有用的墙中,至少有一根柱子比 H 砖高。这提供了一个瞭望台,可以从远处发现僵尸。

这应该排除相当多的可能性,对吗?帮助海蒂计算不符合这些标准的无用墙壁的数量。换句话说,如果每一段的宽度至多为 W,高度至多为 H,那么墙就毫无用处。

参数C,墙的总宽度,与简易版本中的含义相同。但请注意,砖块的数量现在是无限的。

输出无用墙的数量模 106 + 3。

输入

输入的第一行也是唯一一行包含三个空格分隔的整数 C、W 和 H (1 ≤ C ≤ 108、1 ≤ W、H ≤ 100)。

输出

输出不同墙壁的数量,模 106 + 3,根据海蒂的标准,这些墙壁是无用的。

示例

输入 #1

1 1 1

输出 #1

2

输入 #2

1 2 2

输出 #2

3

输入 #3

1 2 3

输出 #3

4

输入#4

3 2 2

输出#4

19

输入 #5

5 4 9

输出 #5

40951

输入 #6

40 37 65

输出 #6

933869

注意

如果任何柱子中都没有砖,则该结构被视为无用的墙。