Ha sortit fa poc la nova raid del WoW, Ny’alotha. En aquesta raid, es va per nivells. En el primer nivell hi ha un monstre, que quan el mates, passes al següent nivell, que hi ha dos monstres. Els pots matar en l’ordre que vulguis pero no pots passar al següent nivell fins que tots son morts. Per complicar la cosa, en alguns nivells hi ha monstres opcionals, que no cal matar-los per a passar al següent nivell. Cada cop que surt una raid, els oficials de tots els clans del WoW discuteixen sobre quin és el millor ordre per a acabar la raid (s’acaba una raid al matar el monstre final de l’últim nivell), però hi ha moltíssimes possibilitats diferents

Entrada

La primera línia indica els casos de prova a considerar. Cada cas de prova són diverses línies. Comença amb un nombre, N, que indica el nombre de nivells que hi ha. Després hi haurà N*2 nombres, per cada nivell, el nombre de monstres obligatoris i el nombre de monstres opcionals. L’últim nivell sempre serà 1 0, perque només hi ha el monstre final.

Sortida

Per cada cas s’haurà de tornar el nombre de combinacions diferents d’ordre de matar als monstres per a passar-se la raid. Recordeu que la raid te la passes un cop has matat tots els monstres obligatoris, sense matar als opcionals. Assumiu que un cop passeu de nivell no torneu mai al nivell anterior a matar els monstres opcionals. Com el número pot ser motl alt (Blizzard pls) es calcularà mòdul 1.000.000.007.

Exemple d'Entrada

5
5
1 0 1 0 1 0 1 0 1 0
3
1 0 3 0 1 0
6
1 0 2 0 4 0 3 0 1 0 1 0
3
1 0 3 1 1 0
5
1 0 2 0 3 1 2 1 1 0 1 0

Exemple de Sortida

1
6
288
30
480

No feu aquest problema. En serio. Feu els altres.