Dico and Bero are two brothers who own a pen shop. They pick up different numbers of pens with different colors from the inventory and put them up for sale. Help them find the number of different choices they can make!

Every day one and only one of the following events occur:

• some days Dico brings a box with \(\mathbf{K}\) pens to the inventory.
• some days Bero takes a box with \(\mathbf{K}\) pens from the inventory.
• some days brothers go to the inventory together and see how many differen ways there are to pick \(\mathbf{K}\) pens. Two ways are different if for at least one color they contain different number of pens.

Each box contain pens of the same color but pens from different boxes always have different colors.

Help them by finding the number of ways to choose the given amount of pens on the days they go to the inventory together.

Input

The first line contains integer number \(\mathbf{N}\). Each of the following \(\mathbf{N}\) lines contain an event description in one of the following forms:

• + K: Dico adds a new box with \(\mathbf{K}\) pens.
• - K: Bero removes a box with \(\mathbf{K}\) pens.
• ? K: count the number of ways to choose \(\mathbf{K}\) pens.

Output

For each event of the third type print a line with the number of ways to choose Z pens from the inventory modulo 1000000007 \((10^9+7)\).

Constraints

• \(1 ≤ \mathbf{N} ≤ 3000\)
• \(1 ≤ \mathbf{K} ≤ 3000\)

The inventory contains at least one box with the given number of pens whenever Bero goes to the inventory.

Example

Input:

6
+ 2
+ 3
? 1
? 5
- 3
? 1

Output:

2
1
1