Product

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

For set \(A\), let \[v(A) = \sum_{S \subset A, |S| \equiv 1 \pmod 2}(\prod_{x \in S}x)\]

Initially, \(A\) is empty. Your task is to insert and delete element keeping track of value of \(v(A)\).

Input

The first line contains the only integer \(q\), which denotes the number of operations.

The following \(q\) lines, which is either "insert \(x\)" or "delete \(x\)".

For convinience, one can assume that \(A\) is a multiset and there are no delete operations for non-exist elements.

\((1 \leq q \leq 10^5, 2 \leq x \leq 10^9)\)

Output

After each operation, print a single integer showing \(v(A) \bmod (10^9 + 7)\).

Sample Input

4
insert 2
insert 3
insert 4
delete 3

Sample Output

2
5
33
6

Hint

After \(4\) is inserted, \(A = \{2, 3, 4\}\). Thus, \(v(A) = 2 + 3 + 4 + 2 \cdot 3 \cdot 4 = 33\).

Source

ftiasch

Manager

Information
Solved Number18
Submit Number95
Problem Tags
number theory
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel