D. Книга заявок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим упрощенную версию книги заявок некоторой акции.

Книга заявок — это список заявок (предложений) от людей, которые хотят купить или продать одну акцию, каждая заявка описывается направлением (BUY или SELL) и ценой.

В каждый момент времени у любой SELL заявки цена больше, чем у любой BUY заявки.

В этой задаче цены всех когда-либо существовавших заявок различны.

Заявка с направлением SELL с наименьшей ценой и заявка с направлением BUY с наибольшей ценой называются лучшими предложениями и выделены черной рамкой на рисунке.

Данная книга заявок говорит, что кто-то хочет продать акцию по цене $$$12$$$, и это лучшее предложение с направлением SELL, потому что у других двух заявок с этим направлением цена выше. У лучшего BUY предложения цена $$$10$$$.

В книге заявок возможны два события:

  1. Кто-то добавил новую заявку с некоторым направлением и некоторой ценой
  2. Кто-то принял лучшее SELL или BUY предложение (совершил сделку). Нельзя принять не лучшее предложение (совершать сделку по менее выгодной цене). После того, как лучшее предложение принято, оно навсегда удаляется из книги заявок.

Можно добавлять новые заявки BUY только с ценами ниже лучшего SELL предложения (если вы хотите купить по более высокой цене, то вместо постановки заявки нужно принять лучшее SELL предложение). Аналогично нельзя добавлять SELL заявки с ценами меньшими или равными лучшему предложению BUY. К примеру, нельзя добавить заявку "SELL $$$20$$$", если уже есть заявка "BUY $$$20$$$" или "BUY $$$25$$$" — в этом случае нужно просто принять лучшее предложение BUY.

У вас есть поврежденный лог событий в книге заявок (в начале никаких заявок в книге нет). В логе есть события двух типов:

  1. "ADD $$$p$$$" означает добавление новой заявки с ценой $$$p$$$ и неизвестным направлением. Заявка не должна противоречить еще не удаленным заявкам в книге заявок.
  2. "ACCEPT $$$p$$$" означает принятие существующего лучшего предложения с ценой $$$p$$$ и неизвестным направлением.

Направления всех заявок (BUY или SELL) в логе утеряны. Не всегда по имеющимся данным можно однозначно восстановить эти направления. Посчитайте количество способов корректно восстановить направления ADD заявок так, что описанные условия всегда выполнены. Ответ может быть очень большим, поэтому выведите его по модулю $$$10^9 + 7$$$. Если невозможно корректно восстановить направления, то выведите $$$0$$$.

Входные данные

В первой строке задано целое число $$$n$$$ ($$$1 \le n \le 363\,304$$$) — количество событий в логе.

Каждая из следующих $$$n$$$ строк содержит слово "ACCEPT" или "ADD" и целое число $$$p$$$ ($$$1 \le p \le 308\,983\,066$$$), описывающих тип события и цену.

Все события типа ADD имеют разные цены. Для события ACCEPT гарантируется, что заявка с такой ценой уже была добавлена и еще не был принята (не участвовала в сделках).

Выходные данные

Выведите число способов восстановить направления всех заявок ADD по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
6
ADD 1
ACCEPT 1
ADD 2
ACCEPT 2
ADD 3
ACCEPT 3
Выходные данные
8
Входные данные
4
ADD 1
ADD 2
ADD 3
ACCEPT 2
Выходные данные
2
Входные данные
7
ADD 1
ADD 2
ADD 3
ADD 4
ADD 5
ACCEPT 3
ACCEPT 5
Выходные данные
0
Примечание

В первом примере каждая из заявок может быть и BUY, и SELL.

Во втором примере заявка с ценой $$$1$$$ должна иметь направление BUY, заявка с ценой $$$3$$$ должна иметь направление SELL.