CF1028D Order book
题目描述
我们来考虑某只股票的一个简化版订单簿。订单簿是一个订单（报价）列表，每个订单代表有人想以某个价格买入或卖出一单位该股票。每个订单由方向（BUY 或 SELL）和价格描述。
在任意时刻，所有 SELL 报价的价格都高于所有 BUY 报价的价格。
在本题中，任意两个曾经存在过的订单都不会有相同的价格。
最低价的 SELL 订单和最高价的 BUY 订单被称为最优报价，如下图中用黑框标出。
如图所示，某人以价格 $12$ 卖出产品，这是最优的 SELL 报价，因为另外两个 SELL 报价价格更高。最优的 BUY 报价价格为 $10$。
在这个订单簿中有两种可能的操作：
1. 有人以某个方向和价格添加一个新订单。
2. 有人以最优的 SELL 或 BUY 报价成交（达成交易）。只能接受最优的 SELL 或 BUY 报价（即以最优价格成交），不能以更差的价格成交。成交后，该订单会从订单簿中永久移除。
只允许添加价格低于当前最优 SELL 报价的 BUY 订单（如果你想以更高的价格买入，则应直接接受最优 SELL 报价而不是添加新订单）。同理，也不能添加价格小于等于当前最优 BUY 报价的 SELL 订单。例如，如果已经有 "BUY $20$" 或 "BUY $25$" 的订单，则不能再添加 "SELL $20$" 的订单——此时应直接接受最优 BUY 报价。
你有一份损坏的订单簿日志（初始时订单簿为空）。每个操作有两种类型：
1. "ADD $p$" 表示以价格 $p$ 添加一个新订单，但方向未知。该订单不能与当前订单簿中尚未移除的订单矛盾。
2. "ACCEPT $p$" 表示以价格 $p$ 接受一个已存在的最优报价，但方向未知。
所有操作的方向信息都丢失了。日志中的信息并不总能完全确定这些方向。请你计算有多少种方式可以为所有 ADD 操作正确恢复方向，使得在任意时刻所有描述的条件都被满足。由于答案可能很大，请输出对 $10^9+7$ 取模的结果。如果无法正确恢复方向，则输出 $0$。
输入格式
第一行包含一个整数 $n$（$1 \le n \le 363\,304$），表示日志中的操作数。
接下来的 $n$ 行，每行包含一个字符串 "ACCEPT" 或 "ADD" 和一个整数 $p$（$1 \le p \le 308\,983\,066$），表示操作类型和价格。
所有 ADD 操作的价格互不相同。对于每个 ACCEPT 操作，保证价格为 $p$ 的订单已经被添加且尚未被接受。
输出格式
输出能够正确恢复所有 ADD 操作方向的方案数，对 $10^9+7$ 取模。
说明/提示
在第一个样例中，每个订单都可以是 BUY 或 SELL。
在第二个样例中，价格为 $1$ 的订单必须是 BUY，价格为 $3$ 的订单必须是 SELL。
由 ChatGPT 4.1 翻译