题目描述

The problem set document for the Yokohama Chinatown Gluttony Contest was kept in a safe at the headquarters of the Kanagawa Gourmendies Foundation. It was considered to be quite secure, but, in the morning of the very day of the contest, the executive director of the foundation found that the document was missing!

The director checked that the document was in the safe when she left the headquarters in the evening of the day before. To open the door of the headquarters office, a valid ID card has to be touched on the reader inside or outside of the door. As the door and its lock are not broken, the thief should have used a valid ID card.

Normally, all the entries and exits through the door are recorded with the ID. The system, however, has been compromised somehow, and some of the recorded ID’s are lost.

It is sure that nobody was in the office when the director left, but, many persons visited the office since then to prepare the contest materials. It is sure that the same ID card was used only once for entry and then once for exit.

The director is planning inquiries to grasp all the visits during the night. You are asked to write a program that calculates the number of possible combinations of ID’s to fill the lost parts of the records.

输入格式

The input consists of a single test case of the following format.

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

The first line contains an integer $n$ ($1 \le n \le 5000$), representing the number of visitors during the night. Each visitor has a unique ID numbered from $1$ to $n$. The following $2n$ lines provide (incomplete) entry and exit records in chronological order. The $i$-th line ($1 \le i \le 2n$) contains a character $c_i$ and an integer $x_i$ ($0 \le x_i \le n$). Here, $c_i = \text{I}$ and $\text{O}$ indicate some visitor entered and exited the office, respectively. $x_i$ denotes the visitor ID, where $x_i \ge 1$ indicates the ID of the visitor is $x_i$, and $x_i = 0$ indicates the ID is lost. At least one of them is $0$. It is guaranteed that there is at least one consistent way to fill the lost ID(s) in the records.

输出格式

Output a single integer in a line which is the number of the consistent ways to fill the lost ID(s) modulo $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