Keine is a teacher and recently she is preparing the test paper of the mid-term test of mathematics. The main content is the vector operation. She has already made some formulas before. Those formulas are about the most common vector operations:

- Scalar multiplication '*' : number * vector = vector, vector * number = vector, number * number = number
- Dot product '.' : vector . vector = number.
- Cross product '^' : vector ^ vector = vector.

In Gensokyo, there is another amazing operation:

- Gensokyo product '!': number ! number = number ! vector = vector ! number = vector, vector ! vector = number.

Unfortunately Keine forgot to add brackets before printing the test paper. What's worse is that she hasn't teached her students the priority of these four operations. So she thinks it's necessary to prepare all possible answers. Now she wants to know the number of available compuation sequences and requires your help.

You don't want to be CAVED, do you?

There are multiple cases.

The first line of input is an integer `n` (1 ≤ `n` ≤ 20) which indicates the cases of test data.

The following `n` lines each contain a nonempty string consisted of '*', '.', '^', '!', lower letters and digits. The length of each string will be less than 10^{5}.

The meaning of '*', '.' '^' and '!' are described above. There are at most 100 operators('*', '.', '^', '!'). Consecuive letters represent a vector and consecutive digits represent a number.

It is confirmed that operators are not adjacent. There is always an operator between vector and number.

For each case, please output the number of available computation sequences. It may be very large, so you must output the answer modulo 10^{9} + 7.

提交代码