Goku has finally got some time to rest, after fighting all his enemies and completing all his training.

He is going to eat his lunch now. While he was enjoying his lunch, his son Gohan came to him with another problem. Goku, being a very caring father, left his lunch and went with Gohan to solve the problem.

Goku finds that the problem is created by his second son, Goten, who has created a mess in his room. Goten has taken all the books which he had and has taken out all the lowercase alphabets from them, and is wondering in how many different ways can he arrange them into one string. He only knows the number of alphabets he has, and he also knows, whether each of the vowels appeared even number of times or odd number of times.

Can you give the answer to the problem?

Note : Only the 26 lowercase alphabets are considered.

Input :

First line contains an integer, t, the number of test cases.
Each test case contains 6 space separated integers, n,a,e,i,o,u in a separate line, where
n = number of alphabets.
a = 1 means 'a' appears odd number of times,
a = 0 means 'a' appears even number of times.
Similarly for other vowels (e,i,o,u).

Output :

For each test case, print the answer to the problem in a single line. As the answer may be large, print it modulo 10⁹ + 7

Constraints :

1 ≤ t ≤ 100
1 ≤ n ≤ 10¹²
a,e,i,o,u is one of {0,1}