#1137. JM的算术表达式（3）

(本题数据有误，暂未修复）

今天JM要求你完成大量的小学数学题，如果你不能按时正确地完成就会被JM用黑魔法变成皮皮虾，然后被czq和flh抓去做成炸虾球。为了不被吃掉，你必须解决如下问题：

给定 组算术表达式，要求你算出每个表达式的结果。由于结果可能很大，你需要输出的是对 取模的结果。

输入的表达式均满足：

• 表达式以中缀表达式的格式给出，每个词素（运算符或操作数）之间用零至三个空格隔开，表达式的首尾两端无多余空格；

• 表达式可能是非法的；

• 表达式包括 + , - , * , / 四种运算符，分别表示加减乘除，其中除法运算需要向下取整；

• 表达式包括 ^ 运算符，表示乘方运算，例如 x ^ y 表示 ；

• 表达式包括 ( , ) 括号；

• 表达式中的操作数为 范围内的整数；

• 表达式中的操作数的个数不超过 ；

• 表达式中的左右括号的总个数不超过 。

关于 ^ 运算符：

• 乘方运算的优先级高于加减乘除，例如 2 ^ 3 * 4 等价于 (2 ^ 3) * 4 ；

• 乘方运算自右向左结合，例如 2 ^ 3 ^ 2 等价于 2 ^ (3 ^ 2) ；

• 当幂次为负数时，需转换为模意义下等价的在 范围内的非负数进行计算，例如 2 ^ (1 - 2) 在计算时等同于 2 ^ 1000000006 。

如果表达式非法，则仅限于以下几种错误中的一种或多种：

• 发生除以零的错误；

• 运算符和操作数不匹配，例如 2 + 3 4 ， 2 + 3 * - 5 和 + 1 等；

• 括号不能正确匹配，例如 1 + 2) ， 5 * (6 / (4 - 1) 等。

第一行一个正整数 ，表示算术表达式的个数。

接下来 行，每行一个字符串，给出一个符合题意的算术表达式。

输出 行，每行一个整数，依次表示每个算术表达式的计算结果（对 取模）。如果表达式非法，则输出 GG 。

样例输入

10
14/  5+2 * (3 - 1)
2^3 ^ 2
(2 ^ 3) ^ 2
5*2 ^ 5-4
( ((7 * (2 - 5) ) )/ 2 )
6 /0
2 ^ (3 - 4)
-1
2 + - 3
5 * (6 / (4 - 1)

样例输出

600000011
512
64
156
499999993
GG
1
GG
GG
GG