You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一场比赛需要一个正常题。

题目描述

有两个集合 $A,B$,要求所有时刻$A$中元素小于$B$中元素，定义两种操作。

ADD：把$x$插入任意一个集合。

ACCEPT：把元素$x$从集合中删除，要求删除的必须是$A$中的最大值或者$B$中的最小值。

求插入集合的方案数，对$10^9+7$取模。

温馨提示

算是对题的解释吧，对于每次插入操作，你可以选择插入到$A$或者$B$中，但是，你需要时刻保证两个限制合法，即$A< B$的限制和删除的限制。我们所求的就是你插入的方案数。

输入格式

第一行一个整数$n$，代表操作个数。

接下来$n$行，每行一个操作。

输出格式

一行一个整数，插入的方案数。

6
ADD 1
ACCEPT 1
ADD 2
ACCEPT 2
ADD 3
ACCEPT 3

8

4
ADD 1
ADD 2
ADD 3
ACCEPT 2

2

7
ADD 1
ADD 2
ADD 3
ADD 4
ADD 5
ACCEPT 3
ACCEPT 5

0

数据范围

对于 $10\%$ 的数据 $n\le17$。

对于 $30\%$ 的数据 $n\le1000$。

对于 $80\%$ 的数据 $n\le100000$。

对于 $100\%$ 的数据 $n\le300000,x\le1e9$，保证$x$不相同，删除的数一定存在于某一集合。