问题陈述
Suposupo 博士开发了一种名为 Shipura 的编程语言。 Shipura 仅支持一个二元运算符 ${\tt >>}$ 和一个一元函数 ${\tt S<\ >}$。
$x {\tt >>} y$ 计算为 $\lfloor x / 2^y \rfloor$(即不超过 $x / 2^y$ 的最大整数),${\tt S<} x {\tt >}$ 计算为 $x^2 \bmod 1{,}000{,}000{,}007$(即,当$x^2$ 除以 $1{,}000{,}000{,}007$)。
运算符 ${\tt >>}$ 是左关联的。例如,表达式 $x {\tt >>} y {\tt >>} z$ 被解释为 $(x {\tt >>} y) {\tt >>} z$,而不是 $x {\tt >>} (y {\tt >>} z)$。请注意,这些括号不会出现在实际的 Shipura 表达式中。
Shipura 的语法(采用 BNF;巴科斯-诺尔范式)如下:
expr ::= term | expr sp ">>" sp term term ::= number | "S" sp "<" sp expr sp ">" sp ::= "" | sp " " number ::= digit | number digit digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
该语法的起始符号是 $\tt expr$,表示 Shipura 中的表达式。此外,$\tt number$ 是 $0$ 到 $1{,}000{,}000{,}000$ 之间的整数,且不带额外的前导零。
编写一个程序来计算 Shipura 表达式。
输入
输入是一系列数据集。每个数据集都由一条线表示,其中包含 Shipura 中的有效表达式。
包含单个 ${\tt \#}$ 的行表示输入的结束。您可以假设数据集的数量最多为 $100$,并且输入文件的总大小不超过 $2{,}000{,}000$ 字节。
输出
对于每个数据集,输出一行包含表达式的计算值。
示例输入
S< S< 12 >> 2 > > 123 >> 1 >> 1 1000000000 >>129 S<S<S<S<S<2>>>>> S <S< S<2013 >>> 11 >>> 10 > #
样本输入的输出
81 30 0 294967268 14592400