Sổ lệnh

Xét một phiên bản đơn giản của sổ lệnh (order book) cho một loại cổ phiếu. Sổ lệnh là danh sách các lệnh của những người muốn mua hoặc bán một đơn vị cổ phiếu; mỗi lệnh được mô tả bởi một hướng (MUA hoặc BÁN) và một giá.

Tại mọi thời điểm, mọi lệnh BÁN đều có giá lớn hơn mọi lệnh MUA. Trong bài này, không có hai lệnh nào từng tồn tại có cùng giá.

Lệnh BÁN giá thấp nhất và lệnh MUA giá cao nhất được gọi là các lệnh tốt nhất.

Có hai thao tác có thể xảy ra với sổ lệnh:

1. Ai đó thêm một lệnh mới với hướng và giá nào đó.
2. Ai đó khớp lệnh MUA tốt nhất hoặc lệnh BÁN tốt nhất. Không thể khớp một lệnh không phải là lệnh tốt nhất (không ai chịu giao dịch ở mức giá tệ hơn). Sau khi được khớp, lệnh bị xoá khỏi sổ vĩnh viễn.

Chỉ được thêm lệnh MUA với giá nhỏ hơn giá của lệnh BÁN tốt nhất: nếu muốn mua với giá cao hơn thì thay vì thêm lệnh, người đó phải khớp lệnh BÁN tốt nhất. Tương tự, không được thêm lệnh BÁN với giá nhỏ hơn hoặc bằng giá của lệnh MUA tốt nhất. Chẳng hạn, không thể thêm lệnh "BÁN 20" khi trong sổ đã có lệnh "MUA 20" hoặc "MUA 25".

Bạn có trong tay một bản nhật ký sổ lệnh đã bị hỏng (ban đầu sổ không có lệnh nào). Mỗi thao tác trong nhật ký thuộc một trong hai dạng:

1. ADD p: thêm một lệnh mới với giá $p$, hướng không rõ. Lệnh này không được mâu thuẫn với các lệnh vẫn còn trong sổ.
2. ACCEPT p: khớp một lệnh tốt nhất đang có trong sổ với giá $p$, hướng không rõ.

Hướng của mọi thao tác đã bị mất. Thông tin trong nhật ký không phải lúc nào cũng đủ để xác định các hướng đó. Hãy đếm số cách khôi phục hướng cho tất cả các thao tác ADD sao cho mọi điều kiện nói trên đều được thoả mãn tại mọi thời điểm. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$. Nếu không thể khôi phục hướng một cách hợp lệ, in ra 0.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$ là số thao tác trong nhật ký.
• Mỗi dòng trong $n$ dòng tiếp theo chứa xâu ACCEPT hoặc ADD và một số nguyên $p$, mô tả loại thao tác và giá.

Dữ liệu ra

In ra số cách khôi phục hướng của các thao tác ADD theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 363304$
• $1\le p\le 308983066$
• Mọi thao tác ADD có giá đôi một khác nhau.
• Với thao tác ACCEPT, đảm bảo lệnh có cùng giá đó đã được thêm vào và chưa bị khớp.

Ví dụ