Tarkastellaan vielä edellisen tehtävän peliä.

Sinulle annetaan taas korttien määrä n ja pelaajien pisteet lopussa a ja b. Monellako tavalla peli on voinut päättyä tähän tilanteeseen?

Syöte

Ensimmäisellä rivillä on kokonaisluku t: testien määrä.

Tämän jälkeen tulee t riviä, joista jokaisella on kolme kokonaislukua n, a ja b.

Tuloste

Tulosta jokaiseen testiin mahdollisten pelinkulkujen määrä modulo 10^9+7.

Esimerkki

Syöte:

5
3 1 2
2 0 1
5 2 2
9 3 5
4 4 1

Tuloste:

6
0
4200
976757050
0

Selitys: Ensimmäisessä testissä mahdolliset pelinkulut ovat:

• Pelaaja 1 pelaa [1,2,3] ja pelaaja 2 pelaa [2,3,1].
• Pelaaja 1 pelaa [1,3,2] ja pelaaja 2 pelaa [2,1,3].
• Pelaaja 1 pelaa [2,1,3] ja pelaaja 2 pelaa [3,2,1].
• Pelaaja 1 pelaa [2,3,1] ja pelaaja 2 pelaa [3,1,2].
• Pelaaja 1 pelaa [3,1,2] ja pelaaja 2 pelaa [1,2,3].
• Pelaaja 1 pelaa [3,2,1] ja pelaaja 2 pelaa [1,3,2].

Neljännessä testissä on 10976757120 mahdollista pelinkulkua ja tämä luku modulo 10^9+7 on 976757050.

Rajat

Kaikissa osatehtävissä 1 \le t \le 1000 ja 0 \le a,b \le n.

Osatehtävä 1 (3 pistettä)

• 1 \le n \le 4

Osatehtävä 2 (5 pistettä)

• 1 \le n \le 8

Osatehtävä 3 (26 pistettä)

• 1 \le n \le 20

Osatehtävä 4 (28 pistettä)

• 1 \le n \le 100

Osatehtävä 5 (38 pistettä)

• 1 \le n \le 2000