如此多的墙壁设计可供选择!即使对 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
注意
如果任何柱子中都没有砖,则该结构被视为无用的墙。