Mini Liga 2

Mecz koszykówki składa się z czterech kwart. Podczas ich trwania zawodnicy starają się zdobyć jak najwięcej punktów oddając celne rzuty do kosza. W zależności od rodzaju rzutu można zdobyć 1, 2 albo 3 punkty.

Pewna drużyna podczas kolejnych kwart zdobyła odpowiednio p₁, p₂, p₃ i p₄ punkty. Odpowiedz na pytanie, ile jest różnych sekwencji rzutów za 1, 2 lub 3 punkty, które odpowiadają podanemu przebiegowi meczu?

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów danych t ∈ [1, 456976]. W kolejnych t liniach znajdują się zestawy danych.

Każdy zestaw danych składa się z czterech liczb całkowitych p₁, p₂, p₃, p₄ z przedziału [0, 25] odpowiadających liczbie punktów zdobytych w kolejnych kwartach.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać odpowiedź na pytanie, ile jest różnych sekwencji rzutów za 1, 2 lub 3 punkty, które odpowiadają podanemu przebiegowi meczu.

Ponieważ liczba sekwencji rzutów może być duża wystarczy, że wypiszesz jej resztę z dzielenia przez 1000000007.

Przykład

Wejście:

1
3 2 1 4

Wyjście:

56