CF1028D.Order book

Let's consider a simplified version of order book of some stock. The order book is a list of orders (offers) from people that want to buy or sell one unit of the stock, each order is described by direction (BUY or SELL) and price.

At every moment of time, every SELL offer has higher price than every BUY offer.

In this problem no two ever existed orders will have the same price.

The lowest-price SELL order and the highest-price BUY order are called the best offers, marked with black frames on the picture below.

The presented order book says that someone wants to sell the product at price $12$ and it's the best SELL offer because the other two have higher prices. The best BUY offer has price $10$.

There are two possible actions in this orderbook:

1. Somebody adds a new order of some direction with some price.
2. Somebody accepts the best possible SELL or BUY offer (makes a deal). It's impossible to accept not the best SELL or BUY offer (to make a deal at worse price). After someone accepts the offer, it is removed from the orderbook forever.

It is allowed to add new BUY order only with prices less than the best SELL offer (if you want to buy stock for higher price, then instead of adding an order you should accept the best SELL offer). Similarly, one couldn't add a new SELL order with price less or equal to the best BUY offer. For example, you can't add a new offer "SELL $20$" if there is already an offer "BUY $20$" or "BUY $25$" — in this case you just accept the best BUY offer.

You have a damaged order book log (in the beginning the are no orders in book). Every action has one of the two types:

1. "ADD $p$" denotes adding a new order with price $p$ and unknown direction. The order must not contradict with orders still not removed from the order book.
2. "ACCEPT $p$" denotes accepting an existing best offer with price $p$ and unknown direction.

The directions of all actions are lost. Information from the log isn't always enough to determine these directions. Count the number of ways to correctly restore all ADD action directions so that all the described conditions are satisfied at any moment. Since the answer could be large, output it modulo $10^9 + 7$. If it is impossible to correctly restore directions, then output $0$.

我们来考虑某只股票的简化版订单簿（order book）。订单簿是一份由希望买入或卖出一股该股票的人所提交的订单（报价）列表，每个订单由方向（BUY 或 SELL）和价格描述。

在任意时刻，所有 SELL 订单的价格均严格高于所有 BUY 订单的价格。

本题中，任意两个曾经存在过的订单价格均不相同。

最低价的 SELL 订单与最高价的 BUY 订单被称为最优报价（best offers），如下图中以黑色边框标出：

该订单簿表明：有人愿以价格 $12$ 卖出该股票，且这是最优 SELL 报价（因为其余两个 SELL 报价价格更高）；最优 BUY 报价的价格为 $10$。

在此订单簿中，仅允许执行以下两种操作：

1. 某人添加一个具有指定方向和价格的新订单；
2. 某人接受当前最优的 SELL 或 BUY 报价（即达成交易）。不允许接受非最优的 SELL 或 BUY 报价（即不能以更差的价格成交）。一旦某报价被接受，它将永久地从订单簿中移除。

添加新订单时需满足如下约束：

• 仅允许添加价格严格低于当前最优 SELL 报价的 BUY 订单（若你愿意以更高价格买入，则不应添加新 BUY 订单，而应直接接受当前最优 SELL 报价）；
• 同理，仅允许添加价格严格高于当前最优 BUY 报价的 SELL 订单。例如，若订单簿中已存在 “BUY $20$” 或 “BUY $25$”，则你不能添加 “SELL $20$” —— 此时你应直接接受最优 BUY 报价。

现给你一份损坏的订单簿日志（初始时订单簿为空）。每条日志记录属于以下两类操作之一：

1. “ADD $p$” 表示添加一个价格为 $p$ 的新订单，但其方向（BUY/SELL）未知。该订单必须与当前尚未被移除的所有已有订单兼容（即满足前述价格约束）；
2. “ACCEPT $p$” 表示接受一个价格为 $p$ 的现存最优报价，但其方向（BUY/SELL）未知。

所有操作的方向信息均已丢失。仅凭日志内容，有时不足以唯一确定各操作的方向。请计算：有多少种方式可为所有 “ADD” 操作正确指定方向（BUY 或 SELL），使得在任意时刻，上述所有条件均得到满足？由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。若不存在任何合法的方式，请输出 $0$。

The first line contains an integer $n$ ($1 \le n \le 363\,304$) — the number of actions in the log.

Each of the next $n$ lines contains a string "ACCEPT" or "ADD" and an integer $p$ ($1 \le p \le 308\,983\,066$), describing an action type and price.

All ADD actions have different prices. For ACCEPT action it is guaranteed that the order with the same price has already been added but has not been accepted yet.

第一行包含一个整数 $n$（$1 \le n \le 363\,304$），表示日志中操作的数量。

接下来的 $n$ 行，每行包含一个字符串 "ACCEPT" 或 "ADD" 以及一个整数 $p$（$1 \le p \le 308\,983\,066$），分别描述操作类型和价格。

所有 "ADD" 操作的价格互不相同。对于 "ACCEPT" 操作，保证存在一个具有相同价格的订单，该订单此前已被添加，但尚未被接受。

Output the number of ways to restore directions of ADD actions modulo $10^9 + 7$.

输出恢复 ADD 操作方向的方案数，对 $10^9 + 7$ 取模。

In the first example each of orders may be BUY or SELL.

In the second example the order with price $1$ has to be BUY order, the order with the price $3$ has to be SELL order.

在第一个例子中，每个订单可以是买入（BUY）或卖出（SELL）。

在第二个例子中，价格为 $1$ 的订单必须是买入（BUY）订单，价格为 $3$ 的订单必须是卖出（SELL）订单。