← 返回题目列表

AtCoder · recruite_2013_pre_b

B. 块排列

中文机器翻译题面 查看原题
现在,红色方块有 R 个,蓝色方块有 B 个。
你将红色和蓝色方块 1 排列在列中。
  1. 连续的 rn 个以下的方块中, rk 个以上不能是红色方块。
  2. 连续的 bn 个以下的方块中, bk 个以上不能是蓝色方块。
上記 2 个条件全部满足的方块排列方式在 1,000,000,009求余数。 在

入力形式

输入的 1 行显示测试用例数。 T 之后,T 个测试用例将会跟随。
每个测试用例 R B rn rk bn bk 按顺序给出。

出力形式

满足条件的排列方式 1,000,000,009后的余数 在线输出 1 行输出。

入力制限

1≦T≦50
1≦R,B≦20
1≦rn,bn≦9
1≦rk≦rn
1≦bk≦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