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 n dice, and the numbers on their tops (after they've been thrown) are given in the int dice. The i-th element (1-based) of dice is equal to the number of dice that were dropped with the number i on top.
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. Return this number modulo 10007. Two lines are different if:
1. They have different lengths.
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.