← 返回题目列表

AtCoder · icpc2013autumn_f

F. 希普拉

中文机器翻译题面 查看原题

问题陈述

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