AT_recruite_2013_pre_b ブロック並べ
题目描述
现在有 $R$ 个红色方块和 $B$ 个蓝色方块。你需要将红色和蓝色方块排成一行。
1. 在任意连续不超过 $rn$ 个方块的区间内，红色方块的数量不能不少于 $rk$ 个。
2. 在任意连续不超过 $bn$ 个方块的区间内，蓝色方块的数量不能不少于 $bk$ 个。
请计算满足上述两个条件的方块排列方案数，并对 $1,000,000,009$ 取模。输入的第 $1$ 行为测试用例数 $T$，接下来有 $T$ 组测试用例。
每组测试用例依次给出 $R$、$B$、$rn$、$rk$、$bn$、$bk$。
对于每组测试用例，输出满足条件的排列方案数对 $1,000,000,009$ 取模后的结果，每组输出占一行。
$1 \leq T \leq 50$
$1 \leq R, B \leq 20$
$1 \leq rn, bn \leq 9$
$1 \leq rk \leq rn$
$1 \leq bk \leq bn$
示例输入：
```
6
3 4 2 2 4 3
2 7 5 4 6 5
5 5 4 3 4 3
8 1 9 8 3 2
1 4 2 2 5 5
20 20 9 8 8 7
```
示例输出：
```
1
3
4
0
5
299856304
```
输入格式
第一行包含一个整数 $T$，表示测试用例数。
接下来 $T$ 行，每行包含六个整数 $R$、$B$、$rn$、$rk$、$bn$、$bk$，分别表示红色方块数量、蓝色方块数量、红色方块限制区间长度、红色方块最小数量、蓝色方块限制区间长度、蓝色方块最小数量。
输出格式
对于每组测试用例，输出一行一个整数，表示满足条件的排列方案数对 $1,000,000,009$ 取模的结果。
说明/提示
- 由于 $R$ 和 $B$ 的范围较小，可以考虑使用动态规划枚举所有可能的排列方式。
- 注意连续区间的限制条件，需要在状态转移时进行判断。
由 ChatGPT 4.1 翻译