Izolarea i-a determinat pe Dorel și pe consătenii lui să desfășoare tot felul de activități casnice. Fiecare locuitor i al comunei a stat în izolare z[i] zile, timp în care a plimbat de c[i] ori câinele, și de p[i] ori pisica.

Cerința

Pentru fiecare locuitor al comunei să se afle în câte moduri putea să-și desfășoare acest program, știind că pisica și câinele trebuie plimbate cel puțin o dată pe zi, fiecare.

Date de intrare

Fișierul de intrare iz.in conține pe prima linie numărul n de locuitori ai comunei lui Dorel, iar pe următoarele n linii, pentru fiecare locuitor i al comunei, câte trei numere naturale, z[i] c[i] p[i].

Date de ieșire

Fișierul de ieșire iz.out va conține pe prima linie n numere naturale, separate prin câte un spațiu, reprezentând numărul de moduri de desfășurare a programului în cele z[i] zile, pentru fiecare locuitor.

Restricții și precizări

• 1 ≤ n ≤ 1.000
• 1 ≤ z[i] ≤ c[i] , p[i] ≤ 1.000.000
• ordinea în care un locuitor plimbă câinele și pisica într-o zi nu are importanță
• rezultatele se vor afișa modulo 1.000.000.007

Exemplu:

iz.in

2
2 3 2
3 5 4

iz.out

2 18

Explicație

Primul locuitor are următoarele variante pentru desfășurarea programului de izolare: [ccp,cp] sau [cp,ccp].

Al doilea: [ccpp,ccp,cp], [ccp,ccpp,cp], [ccp,ccp,cpp], [cpp,ccp,ccp], [cp,ccpp,ccp], [cp,ccp,ccpp], [ccpp,cp,ccp], [ccp,cpp,ccp], [ccp,cp,ccpp], [cccpp,cp,cp], [cccp,cpp,cp], [cccp,cp,cpp], [cpp,cccp,cp], [cp,cccpp,cp], [cp,cccp,cpp], [cpp,cp,cccp], [cp,cpp,cccp], [cp,cp,cccpp].

Legendă rurală: c – câine, p – pisică