21934번 - High-Tech Detective 다국어

문제

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.

n
c1 x1
.
.
.
c2n x2n

The first line contains an integer n (1 ≤ n ≤ 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 ≤ i ≤ 2n) contains a character c_i and an integer x_i (0 ≤ x_i ≤ n). Here, c_i denotes the type of the event, where c_i = I and O indicate some visitor entered and exited the office, respectively. x_i denotes the visitor ID, where x_i ≥ 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⁹ + 7.

제한

힌트