logo AlgoBeat OnlineJudge
登录 注册

#10028. [ICPC 2016 NAIPC] Mountain Scenes

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Dr_KC_Haus

题目描述

一位艺术家从一卷宽为 英寸的丝带开始。她将丝带剪成若干段,每段的长度都是整数英寸,然后将这些丝带段对齐相框的底部,垂直地排列在各列中,从而形成一幅山景图。山景图必须是高低不平的;如果所有列的高度都相同,那就是一幅平原图,而不是山景图!艺术家可能不会使用整卷丝带。

如果艺术家有 英寸长的丝带和一个 英寸的相框,她可以创作出以下山景图:

她不会创作出以下这些图,因为它们不是山景图,而是平原图:

给定丝带的长度、相框的宽度和高度(单位均为英寸),请问艺术家可以创作出多少种不同的山景图?如果两个场景中丝带覆盖的区域不同,则视为不同的场景。注意,任何一列中放置的丝带段不能超过一段。

输入格式

每个输入包含单个测试用例。请注意,你的程序可能会在不同输入上多次运行。输入只有一行,包含三个空格分隔的整数 ,其中 )是丝带的长度(英寸),)是相框的宽度,)是相框的高度(单位均为英寸)。

输出格式

输出一个整数,表示艺术家可能创作出的山景图的总数,对 取模。

样例

输入输出样例 #1

输入 #1

25 5 5

输出 #1

7770

输入输出样例 #2

输入 #2

15 5 5

输出 #2

6050

输入输出样例 #3

输入 #3

10 10 1

输出 #3

1022

输入输出样例 #4

输入 #4

4 2 2

输出 #4

6

数据范围与提示

本题数据仅为民间数据。