问题描述

小蓝最近设计了一款 “阅后即焚” 数据库，顾名思义这个数据库只有两种操作：增加一条数据和删除一条数据。简言之，这款数据库中只有一个表，且这个表只有两列：$id$ 和 $value$，其中每条数据都有一个独一无二的编号 $id$，$value$ 则是这条数据对应的存储内容。

数据库操作语句有且仅有两种：

• INSERT $id$ $value$：插入一条新的数据，编号为 $id$，内容为 $value$。
• DELETE $id$：删除编号为 $id$ 的数据。

现在给出 $N$ 条数据库语句，我们保证按照给出的语句顺序执行是合法的，合法指的是：INSERT 时数据库中一定不存在编号为 $id$ 的数据，DELETE 时数据库中一定存在编号为 $id$ 的数据，且同一个编号 $id$ 不会被 INSERT / DELETE 多次。

你可以任意调整这些语句的执行顺序，现在请问一共有多少个不同的语句执行顺序，能够使得调整之后的语句顺序依旧是合法的并且按序执行之后数据库内容和给出的初始语句顺序执行后的结果一致。结果一致指的是二者包含的 $id$ 集合是相同的，并且相同的 $id$ 对应的 $value$ 也是相同的。

输入格式

第一行一个整数 $N$ 表示有 $N$ 条数据库语句。

接下来输入 $N$ 行，每行一条数据库语句。

输出格式

一行一个整数，表示答案。由于答案可能过大，请将答案对 $1000000007$ 取模之后输出。

4
INSERT 1 1
INSERT 2 2
DELETE 1
DELETE 2

6

样例说明

一共有 6 种不同的排列方式：

评测用例规模与约定

对于 $30\%$ 的评测用例：$1≤N≤10$。

对于 $60\%$ 的评测用例：$1≤N≤1000$。

对于 $100\%$ 的评测用例：$1≤N≤10^5$，$id$ 和 $value$ 均是 $32$ 位有符号整数。