B - ブロック並べ

Time Limit: 20 sec / Memory Limit: 256 MB

いま、赤のブロックが 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