题目描述

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的,例如：8-(3+2*6)/5+4

其计算结果为：9

编写一个程序，求出表达式的值。

输入格式

就一行，是一个中缀表达式。输入的符号中只有这些基本符号 0123456789+-*/^()，并且输入的数字为正整数。

所输入的字符串不要判错。

输出格式

一行只有一个数字，表示运算结果，最后的值 mod 1313131313。

8-(3+2*6)/5+4

9

2^2^3

256

提示

运算的结果可能为负数，/ 以整除运算。并且中间每一步都不会超过 $2^{31}$。字符串长度不超过 $1000000$。

注意乘方运算 ^ 是从右向左结合的，即 2 ^ 2 ^ 3 为 2 ^ (2 ^ 3)，后缀表达式为 2 2 3 ^ ^。

其他同优先级的运算是从左向右结合的，即 4 / 2 / 2 * 2 为 ((4 / 2) / 2) * 2，后缀表达式为 4 2 / 2 / 2 *。

保证不会出现计算乘方时幂次为负数的情况，故保证一切中间结果为整数。