有两个集合 $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$ 不相同，删除的数一定存在于某一集合。