B - ブロック並べ
Editorial
/ 
いま、赤のブロックが R 個、青のブロックは B 個ある。
あなたは赤と青のブロックを 1 列に並べる。
入力の 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
/ 
Time Limit: 20 sec / Memory Limit: 256 MB
あなたは赤と青のブロックを 1 列に並べる。
- 連続する rn 個以下のブロックのうち、 rk 個以上が赤のブロックになってはいけない。
- 連続する bn 個以下のブロックのうち、 bk 個以上が青のブロックになってはいけない。
入力形式
各テストケースは R B rn rk bn bk の順に与えられる。
出力形式
入力制限
1≦R,B≦20
1≦rn,bn≦9
1≦rk≦rn
1≦bk≦bn
サンプル入力
間違ったサンプル入力がありましたので、一部修正しました。
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
サンプル出力
3
4
0
5
299856304