yummy 正在写一个 $C++$ 程序，程序的开头有 $n$ 行宏定义，具体地，对于 $1\leq i\leq n$，第 $i$ 行只可能是下面四种之一，其中 $a,b,x$ 均为数字：

• #define S_i x，用 $N\ x$ 来表示，保证 $0\leq x<10^9+7$。
• #define S_i S_a<<S_b，用 $<\ a\ b$ 来表示。
• #define S_i S_a+S_b，用 $+\ a\ b$ 来表示。
• #define S_i S_a*S_b，用 $*\ a\ b$ 来表示。

本题中，我们假定程序中的 $int$ 类型可以存储任意大的数字而不发生溢出，并且 $a<<b$ 完全等价于 $a\times 2^b$。

对于每个 $1\leq i\leq n$，计算 cout<<(S_i)<<endl; 的输出对 $10^9+7$ 取余的结果。

保证程序可以在有限时间内编译成功。

输入格式

输入的第一行有一个正整数 $n$（$1\leq n\leq 3\times 10^5$），表示宏定义的行数。

之后 $n$ 行，每行有一个宏定义语句，格式见题目描述。

输出格式

输出 $n$ 行，每行一个自然数，其中第 $i$ 行输出 cout<<(S_i)<<endl; 的结果对 $10^9+7$ 取余的结果。

样例

输入

5
N 3
N 1
< 1 2
+ 5 5
* 3 3

输出

3
1
6
6144
48

提示

因为数值比较小，所以不会发生溢出。选手不难使用如下程序验证：

#define S1 3
#define S2 1
#define S3 S1<<S2
#define S4 S5+S5
#define S5 S3*S3

#include<bits/stdc++.h>
using namespace std;
int main(){
  cout<<(S1)<<endl;
  cout<<(S2)<<endl;
  cout<<(S3)<<endl;
  cout<<(S4)<<endl;
  cout<<(S5)<<endl;
  return 0;
}