thegrade

AlekuKebap is in his math class. While he tries to figure out why $1+1=2$, his teacher was writing on the board a slightly more complicated problem. There are given $Q$ queries and a list $S$ with $P$ elements equal with $0$. Let $A$ be initially an empty set. The queries can be:

• $0 \ x$ (insert value $x$ in set $A$)
• $1 \ x$ (erase the value $x$ from set $A$, it is guaranteed that the value $x$ exists in set $A$)

It is guaranteed that $A$ will never be empty after a query. After every query, the teacher asks Aleku the following question: can I arrange in list $S$ all elements from the set $A$ (not necessary in the order from the A) so that:

• Elements form $A$ will be put on distinct standings, the rest being occupied by $P$ elements equal to $0$
• Let $S_i$ be a positive element from $S$ and $S_j$ the closest positive element from $S$ that is located to the left of $S_i$, then the following condition must be respected: $i-j \geq S_i$.
• Let $f$ be the first positive element from the left of $S$, then $f \geq S_f$.

If the answer to this question is yes, then find how many different configurations can be obtained. Because the answer can be very big, print the answer modulo $1 \ 000 \ 000 \ 007$ . If the answer is no, print $-1$.

Task

Help AlekuKebap to answer correctly to all teacher’s questions to recive a 10 grade. His averave depends on this grade!!

Input

The first line contains two integers $Q$ and $P$.

The next $Q$ lines contain the description of every query.

Output

Every line will contain the answer to every question from the $Q$ questions.

Restrictions

• You have to print the answer modulo $1 \ 000 \ 000 \ 007$.
• All numbers that will be added in the set are $\leq 1 \ 000 \ 000$.
• WARNING! If the answer for a query is no, print $-1$!!!
• WARNING! Alecu is not a kebap, he is a human being but this is his name. He is actually a captain... THE CAPTAIN.

Example

stdin

9 8
0 3
0 3
0 2
1 2
0 1
0 1
0 1
1 3
1 1 

stdout

6
6
3
6
12
6
-1
60
60