← 返回题目列表

Codeforces · 306/C

C. 又白又黑又白

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

波利卡普斯确信他的生活符合描述:“首先有一条白色条纹,然后是一条黑色条纹,然后又是一条白色条纹”。因此,Polycarpus 确信这条规则将在接下来的 n 天内实现。波利卡普斯知道他会遇到好事和坏事。每天至少会发生一项活动。由于每一天都明确地被描述为白色或黑色条纹的一部分,因此每一天只会发生相同类型的事件(无论是好还是不太好)。

如果 Polycarpus 出现白色条纹(只有好的事件的条纹,条纹的长度至少为 1 天)、黑色的条纹(只有不太好的事件的条纹,条纹的长度至少为 1 天)和再次的白色条纹(只有好的事件的条纹,条纹的长度),那么在接下来的 n 天内,这种情况会出现多少种不同的方式至少 1 天)。 n 天中的每一天都只属于三个条纹之一。

请注意,即使是同一类型的事件也彼此不同。即使某些事件发生在同一天,它们也会按某种顺序发生(没有同时发生的事件)。

编写一段代码,打印可能的配置数量,以将事件按天排序。请参阅示例以了解哪些场景应被视为不同的场景。打印答案模 1000000009 (109 + 9)。

输入

输入的单行包含整数 n、w 和 b (3 ≤ n ≤ 4000, 2 ≤ w ≤ 4000, 1 ≤ b ≤ 4000) — 天数、好事件数和不太好事件数。保证w+b≥n。

输出

打印所需的路数模 1000000009 (109 + 9)。

示例

输入 #1

3 2 1

输出 #1

2

输入 #2

4 2 2

输出 #2

4

输入 #3

3 2 2

输出 #3

4

注意

我们将用从 1 开始的数字来表示好的事件,用从 'a' 开始的字母来表示不太好的事件。垂直线分隔日期。

在第一个示例中,可能的方式是:“1|a|2”和“2|a|1”。在第二个示例中,可能的方式是:“1|a|b|2”、“2|a|b|1”、“1|b|a|2”和“2|b|a|1”。在第三个示例中,可能的方式是:“1|ab|2”、“2|ab|1”、“1|ba|2”和“2|ba|1”。