Description

横滨中华街暴食大赛的题目文件被保存在神奈川美食基金会总部的保险箱中。它本被认为相当安全，但在比赛当天的早晨，基金会的执行主任发现文件不翼而飞！

主任确认她在前一天晚上离开总部时文件还在保险箱里。要打开总部办公室的门，必须在门内或门外的读卡器上刷一张有效的 ID 卡。由于门和锁都没有损坏，窃贼应该使用了有效的 ID 卡。

正常情况下，所有通过这扇门的进出记录都会与 ID 一起被记录下来。然而，系统不知何故出现了故障，导致部分记录的 ID 丢失了。

可以确定主任离开时办公室里没有人，但之后有许多人为了准备比赛材料而访问了办公室。可以确定的是，同一张 ID 卡只被用于一次进入和随后的一次离开。

主任正计划进行调查，以了解夜间的所有访问情况。你被要求编写一个程序，计算填充记录中丢失部分 ID 的可能组合数量。

Input Format

输入包含单个测试用例，格式如下。

$$\begin{aligned} &n\\ &c_1 \ x_1\\ &\vdots\\ &c_{2n} \ x_{2n}\\ \end{aligned}$$

第一行包含一个整数 $n$ （$1 \le n \le 5000$），表示夜间的访客数量。每位访客都有一个唯一的 ID，编号从 $1$ 到 $n$。接下来的 $2n$ 行按时间顺序提供了（不完整的）进入和离开记录。第 $i$ 行（$1 \le i \le 2n$）包含一个字符 $c_i$ 和一个整数 $x_i$ （$0 \le x_i \le n$）。这里，$c_i = \text{I}$ 和 $\text{O}$ 分别表示有访客进入和离开办公室。$x_i$ 表示访客 ID，其中 $x_i \ge 1$ 表示访客的 ID 是 $x_i$，$x_i = 0$ 表示 ID 丢失。至少有一个 $x_i$ 为 $0$。保证至少存在一种一致的方式来填充记录中丢失的 ID。

Output Format

输出一行一个整数，表示填充丢失 ID 的一致方式的数量对 $10^9 + 7$ 取模后的结果。

4
I 1
I 0
O 0
I 0
O 2
I 4
O 0
O 4

3

3
I 0
I 0
I 0
O 0
O 0
O 0

36