Evaluate Expression
题号：NC221781
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Moca is learning how to evaluate a mathematical expression, and she is only able to evaluate a complicated expression step by step. But she is very good at counting, so she is curious about how many different orders evaluate a given expression.

In this problem, you only need to consider some simple mathematical expressions consisting of ,  (addition), (multiplication) and . Multiplication has a higher priority than addition. Parentheses can be used to indicate an alternative order. In each step of the evaluation, Moca can choose an operation (addition or multiplication) and replace it with the corresponding result. Notice that Moca can not break the original priority, which may cause her to evaluate an incorrect result. For example, Moca can not choose to evaluate the middle addition in and the middle multiplication in . If many different operations can be evaluated valid, she can choose any one of them.

Moca is very curious. Can you help her count the number of different valid orders to evaluate the given mathematical expression? Since the answer may be very large, you only need to print the answer modulo .

输入描述:

The first line contains one integer   -- the number of testcases.

For each testcase, there is only one line contains a valid expression   consisting of , ,  and . All the numbers that appear are not greater than  (only one digit). All the  that appear are binary operations ( is invalid).

It is guaranteed that the sum of lengths of all expressions does not exceed .

输出描述:

For each testcase, print the number of valid evaluation order modulo  in one line.
示例1

输入

复制 
3
1+1+1+1
1*2*3+4*5
1+(2*3*4+5+6)*6+7*8*9

输出

复制 
6
6
784

说明


In the first example,  has  valid evaluation orders:

1.\underline{1+1}+1+1 \to \underline{2+1}+1 \to \underline{3+1} \to 4
2.\underline{1+1}+1+1 \to 2+\underline{1+1} \to \underline{2+2} \to 4
3.1+\underline{1+1}+1 \to \underline{1+2}+1 \to \underline{3+1} \to 4
4.1+\underline{1+1}+1 \to 1+\underline{2+1} \to \underline{1+3} \to 4
5.1+1+\underline{1+1} \to 1+\underline{1+2} \to \underline{1+3} \to 4
6.1+1+\underline{1+1} \to \underline{1+1}+2 \to \underline{2+2} \to 4

In the second example, 1 \times 2 \times 3+4 \times 5 has  valid evaluation orders:

1.\underline{1 \times 2} \times 3+4 \times 5 \to \underline{2 \times 3}+4 \times 5 \to 6+\underline{4 \times 5} \to \underline{6+20} \to 26
2.\underline{1 \times 2} \times 3+4 \times 5 \to 2 \times 3+\underline{4 \times 5} \to \underline{2 \times 3}+20 \to \underline{6+20} \to 26
3.1 \times \underline{2 \times 3}+4 \times 5 \to \underline{1 \times 6}+4 \times 5 \to 6+\underline{4 \times 5} \to \underline{6+20} \to 26
4.1 \times \underline{2 \times 3}+4 \times 5 \to 2 \times 3+\underline{4 \times 5} \to \underline{2 \times 3}+20 \to \underline{6+20} \to 26
5.1 \times 2 \times 3+\underline{4 \times 5} \to \underline{1 \times 2} \times 3+20 \to \underline{2 \times 3}+20 \to \underline{6+20} \to 26
6.1 \times 2 \times 3+\underline{4 \times 5} \to 1 \times \underline{2 \times 3}+20 \to \underline{1 \times 6}+20 \to \underline{6+20} \to 26