横滨中华街贪吃大赛的题目集存放在神奈川美食家基金会总部的保险柜里。虽然这被认为是非常安全的，但在比赛当天的早上，基金会的执行董事发现文件不见了！

董事确认，当她前一天晚上离开总部时，文件还在保险柜里。要打开总部办公室的门，必须在门内或门外的读卡器上刷有效的身份证件。由于门和锁都没有损坏，小偷应该使用了有效的身份证件。

通常，所有通过该门的进入和离开都会记录身份证号。然而，系统不知何故遭到了破坏，一些记录的身份证号丢失了。

可以确定的是，董事离开时办公室里没有人，但此后有许多人为了准备比赛材料访问过办公室。可以确定的是，同一张身份证件只用于一次进入和一次离开。

董事正计划进行调查，以掌握夜间所有的访问情况。请你编写一个程序，计算填补记录中丢失部分的身份证件组合数。

输入格式

输入包含一组测试用例，格式如下：

$n$ $c_1 \ x_1$ $\vdots$ $c_{2n} \ x_{2n}$

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

输出格式

输出一行，包含一个整数，表示填补丢失 ID 的一致方案数，对 $10^9 + 7$ 取模。

样例

样例输入 1

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

样例输出 1

3

样例输入 2

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

样例输出 2

36