Counting Valid Reorderings in a Self‐Destruct Database

Little Blue has designed a "read‐and‐burn" database, which supports only two operations on a single table with two columns: \(id\) and \(value\). Each record inserted into the table has a unique \(id\) and an associated \(value\).

The database supports exactly two types of SQL-like operations:

1. \(\text{INSERT } id\ value\): Insert a new record with identifier \(id\) and content \(value\).
2. \(\text{DELETE } id\): Delete the record with identifier \(id\).

You are given \(N\) operations which, when executed in the given order, are guaranteed to be legal. Legality means that:

• At the moment of an INSERT, the record with that \(id\) does not exist in the database.
• At the moment of a DELETE, the record with that \(id\) exists in the database.
• The same \(id\) does not appear in any operation more than once (i.e. each \(id\) is inserted at most once, and if it is deleted, it is deleted only once).

You are allowed to arbitrarily rearrange the order of these operations. However, the rearranged order must still be legal and, after all operations are executed, the final state of the database (which records remain, along with their associated \(value\)) must be identical to that obtained by executing the operations in the original order.

For an \(id\) that appears in both an INSERT and a DELETE operation, the only requirement to maintain legality is that the \(\text{INSERT}\) must come before the corresponding \(\text{DELETE}\) in the rearranged order. Operations concerning different \(id\) values can be arbitrarily interleaved.

Let \(k\) be the number of \(id\)s that appear in both an INSERT and a DELETE (i.e. the number of deletions, since each deletion corresponds to an inserted record). If \(m\) is the number of records that are only inserted (and never deleted), then the total number of operations is \(N = 2k + m\). In any valid reordering, the only constraint is that for each of the \(k\) records, the corresponding INSERT must occur before its DELETE. Thus, the total number of valid reordering is:

[ \frac{N!}{2^{k}} ]

Since \(N!\) can be enormous, output the result modulo \(10^9+7\).

inputFormat

The first line contains a single integer \(N\) (\(1 \leq N \leq 10^5\)), the total number of operations.

The next \(N\) lines each contain an operation in one of the following forms:

• INSERT id value where id is an integer and value is a string (without spaces).
• DELETE id where id is an integer.

It is guaranteed that the operations given in the input are legal.

outputFormat

Output a single integer, the number of valid reorderings that satisfy the constraints, modulo \(10^9+7\).

sample

3
INSERT 1 a
INSERT 2 b
DELETE 1

3