小猿想对一种前缀表达式求值，该表达式定义如下： 1、每个表达式的形式都是 ( operator arg1 arg2 )，即由左括号，运算符，运算数1，运算数2，右括号组成。 2、运算符包括三种，分别是'+', '-', '*'。 3、运算符一定接收两个运算数，运算数间必须通过空格分隔，运算数可以是另外一个表达式或者不带符号的非负整数（小于10000000）。 (- 0 1) 代表 0 - 1； (+ 1 2) 代表 1 + 2； (+ (* 2 3) 1) 也是一个合法的表达式，代表了 2 * 3 + 1 4、在不产生歧义的情况下，空格也可以省略或者冗余。例如， (+ 0 1) 和 ( +0 1) ，( + 0 1 ) 都被认为是合法的输入，且有相同的意义，代表 0 + 1。

输入描述:

第一行包含一个正整数T(T 输入中的表达式只可能有两种不同类型的错误：1.括号不匹配，如+ 1 2没有括号。2.运算符缺失，如(2 3) 没有运算符。

输出描述:

对于合法的表达式，其值为Result，请输出 (Result Mod 10000000 + 10000000) Mod 10000000的结果，对于不合法的表达式，请输出“invalid”。