CF306C White, Black and White Again

Polycarpus 确信他的生活可以用如下描述：“首先是一段白色条纹，然后是一段黑色条纹，接着又是一段白色条纹”。因此，Polycarpus 确信在接下来的 $n$ 天中，这一规则依然适用。Polycarpus 已知他将会有 $w$ 个好事件和 $b$ 个不那么好的事件。每一天至少会有一个事件发生。由于每一天都明确地属于白色或黑色条纹，因此每一天只能有同一种类型的事件（要么全是好事件，要么全是不那么好的事件）。 问：在接下来的 $n$ 天中，共有多少种不同的方式将这些事件分配到每天，满足 Polycarpus 的条纹规律（第一段是仅包含好事件的白色条纹，长度至少为一天；然后是一段仅包含不那么好的事件的黑色条纹，长度至少为一天；最后是一段仅包含好事件的白色条纹，长度也至少为一天）。每一天只能属于上述三段中的一个。 注意，即使是同类型的事件，每个事件也是不同的。如果某天有多个事件，则这些事件是有顺序的（没有同时发生的情况）。 请编写代码，输出将事件分配到每天，共有多少种不同的方案。输出结果对 $1000000009$ 取模。

输入只有一行，包括三个整数 $n$、$w$、$b$（$3 \leq n \leq 4000$，$2 \leq w \leq 4000$，$1 \leq b \leq 4000$）——表示天数、好事件数和不那么好的事件数。保证 $w+b \geq n$。

输出满足要求的分配方案数，结果对 $1000000009$ 取模。

我们用数字从 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”。 由 ChatGPT 5 翻译