첨단 형사

요코하마 차이나타운 대식회 콘테스트의 문제 출제 문서가 카나가와 미식가 재단 본부의 금고에 보관되어 있었다. 상당히 안전하다고 여겨졌지만, 대회 당일 아침 재단 이사장은 문서가 사라진 것을 발견했다!

이사장은 전날 저녁 본부를 떠날 때 문서가 금고에 있었음을 확인했다. 본부 사무실 문을 열려면 유효한 신분증을 문 안쪽이나 바깥쪽의 리더기에 대야 한다. 문과 잠금장치가 부서지지 않았으므로, 도둑은 유효한 신분증을 사용했을 것이다.

보통 문을 통한 모든 출입은 신분증과 함께 기록된다. 그러나 시스템이 어떻게든 침해되어 기록된 신분증 중 일부가 유실되었다.

이사장이 떠날 때 사무실에 아무도 없었음은 확실하지만, 그 후 대회 자료를 준비하기 위해 많은 사람이 사무실을 방문했다. 같은 신분증은 입장에 한 번, 퇴장에 한 번만 사용되었음이 확실하다.

이사장은 밤사이의 모든 방문을 파악하기 위해 조사를 계획하고 있다. 당신은 기록의 유실된 부분을 채울 수 있는 신분증 조합의 수를 계산하는 프로그램을 작성하라는 요청을 받았다.

입력은 다음과 같은 형식의 단일 테스트 케이스로 이루어진다.

n
c1 x1
.
.
.
c2n x2n

첫 줄에는 밤사이 방문자 수를 나타내는 정수 n (1 ≤ n ≤ 5000)이 주어진다. 각 방문자는 1부터 n까지 번호가 붙은 고유한 신분증을 가진다. 다음 2n개의 줄은 시간 순서대로 (불완전한) 입장 및 퇴장 기록을 제공한다. i번째 줄 (1 ≤ i ≤ 2n)은 문자 ci와 정수 xi (0 ≤ xi ≤ n)를 포함한다. 여기서 ci는 사건의 유형으로, ci = I와 O는 각각 어떤 방문자가 사무실에 입장했음과 퇴장했음을 나타낸다. xi는 방문자 신분증으로, xi ≥ 1은 방문자의 신분증이 xi임을 나타내고, xi = 0은 신분증이 유실되었음을 나타낸다. 둘 중 적어도 하나는 0이다. 기록에서 유실된 신분증을 채우는 일관된 방법이 적어도 하나 있음이 보장된다.

유실된 신분증을 채우는 일관된 방법의 수를 109 + 7로 나눈 나머지를 한 줄에 정수로 출력한다.