Time Limit: 5000 MS    Memory Limit: 65536 K 


Description

A game die is a cube with the numbers 1 to 6 written on its sides: 1 - on the top 2 - on the left 3 - on the front 4 - on the back 5 - on the right 6 - on the bottom You have thrown some dice, and the numbers on their tops (after they've been thrown) are given. You want to construct a single straight line using one or more of these thrown dice. Each pair of adjacent dice must have the same number on the sides where they touch each other. You may rotate dice as long as the numbers on their tops don't change. Each die may be used at most once. Determine the number of different ways you can construct a single straight line using the thrown dice. Output this number modulo 10007. Two lines are different if: 1. They have different lengths. OR 2. Orient both lines horizontally and compare them from left to right. If two dice at the same position in each line have different orientations, the lines are different. Note that the lines 1-3-6 and 6-3-1 are considered different under this rule.

Input

The first line of input is the number of test case. For each test case: There is only one line contains six integers Gi. The i-th integer(1-based) of dice is equal to the number of dice that were dropped with the number i on top. There is a blank line before each test case. 0 <= Gi <= 1000

Output

For each test case output the answer on a single line.

Sample Input

4 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1000 1000 1000 1000 1000 1000

Sample Output

0 16 12 6271

Source

8th SCUPC

Author

windy7926778