Республиканская олимпиада по информатике 2017 год, Павлодар

(Бұл данаққа берген соңғы есебім:))

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Бастапқысында жалғыз нөмері 1 төбесінен тұратын екілік данақ берілген. Сізге келесі түрдегі $M$ тапсырысты орындау керек:

• $Grow$ $V$, $V$ төбесінің бұтағындағы барлық $leaf$ деген листтарына нөмері $2 \cdot leaf$ және $2 \cdot leaf+1$ болатын төбелерді қосу.
• $Sum$ $V,$ $V$ төбесінің бұтағындағы барлық төбелердің нөмерлерінің қосындысының $10^9+7$ бөлгендегі қалдығын табу керек.

Сіз бұл есепті шығара аласыз ба?

Формат входного файла

Бірінші жолда жалғыз бүтін сан берілген $M$ $(1 \leq M \leq 2 \cdot 10^5)$ — тапсырыстардың саны. Келесі $M$ жолда тапсырыстардың сипаттамасы берілген. Әрбір тапсырыс бір жолмен сипатталады $Op$ $V$, мұндағы $Op$ — тапсырыстың түрі ($Grow$ немесе $Sum$), ал $V$ — төбенің нөмері.

Формат выходного файла

Барлық $Sum$ деген тапсырыстың түрі үшін керек қосындыны шығарыңыз. Берілген ретімен шығарыңыз.

Система оценки

Есеп 7 бөлімнен тұрады:

1. $1 \leq M \leq 20$. Бұл бөлім $15$ ұпайға бағаланады.
2. $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Grow$ $V$. Бұл бөлім $10$ ұпайға бағаланады.
3. $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Sum$ $V$. Бұл бөлім $10$ ұпайға бағаланады.
4. $1 \leq M \leq 10^3$. Бұл бөлім $15$ ұпайға бағаланады.
5. $1 \leq M \leq 2 \cdot 10^5$, барлық $Sum$ тапсырыстары $Grow$ тапсырыстарынан кейін орындала. Бұл бөлім $15$ ұпайға бағаланады.
6. $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^6$. Бұл бөлім $15$ ұпайға бағаланады.
7. $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^9$. Бұл бөлім $20$ ұпайға бағаланады.

\Example Вход

5
Grow 1
Grow 1
Grow 2
Sum 1
Sum 4

Ответ

66
21

( Nurlan Zhusupov )