AlekuKebap 正在上数学课。当他试图弄明白为什么 $1+1=2$ 时，他的老师在黑板上写下了一个稍微复杂一点的问题。给定 $Q$ 次查询和一个包含 $P$ 个 $0$ 的列表 $S$。设 $A$ 为一个初始为空的集合。查询可以是：

• $0 \ x$（将值 $x$ 插入集合 $A$）
• $1 \ x$（从集合 $A$ 中删除值 $x$，保证值 $x$ 在集合 $A$ 中存在）

保证在每次查询后，$A$ 永远不会为空。在每次查询后，老师问 Aleku 以下问题：我能否将集合 $A$ 中的所有元素排列在列表 $S$ 中（不一定要按照 $A$ 中的顺序），使得：

• $A$ 中的元素被放置在不同的位置上，其余位置由 $P$ 个等于 $0$ 的元素占据。
• 设 $S[i]$ 是 $S$ 中的一个正元素，$S[j]$ 是位于 $S[i]$ 左侧且距离 $S[i]$ 最近的正元素，则必须满足以下条件：$i-j \ge S[i]$。
• 设 $f$ 是从左侧开始 $S$ 中的第一个正元素，则 $f \ge S[f]$。

如果这个问题的答案是肯定的，那么找出可以获得多少种不同的配置。因为答案可能非常大，请输出答案对 $1\,000\,000\,007$ 取模的结果。如果答案是否定的，请输出 $-1$。

任务

帮助 AlekuKebap 正确回答老师的所有问题以获得 10 分。 他的平均成绩取决于这个分数！！

输入格式

第一行包含两个整数 $Q$ 和 $P$。 接下来的 $Q$ 行包含每次查询的描述。

输出格式

每一行将包含对 $Q$ 个问题中每一个问题的回答。

子任务

• 你必须输出答案对 $1\,000\,000\,007$ 取模的结果。
• 所有将被添加到集合中的数字均 $\le 1\,000\,000$。
• 警告！！！如果查询的答案是否定的，请输出 $-1$！！！
• 警告！！！Alecu 不是一个烤肉（kebap），他是一个人类，但这只是他的名字。他实际上是一位船长……那位船长。

样例

输入格式 1

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

输出格式 1

6
6
3
6
12
6
-1
60
60