题目描述

维护一个正整数多重集合 $S$，初始为空，支持两个操作：

• 插入：插入一个新数 $x$。
• 修改：令集合中所有数加 $1$。

每次操作结束后，计算 $S$ 中所有数的 $k$ 次方和，$k$ 预先给定。

和可能很大，你只需要输出它对 $10^9+7$ 的余数即可。

输入格式

第一行两个数 $M,k$，其中 $M$ 表示操作次数。

接下来 $M$ 行，每行可能为以下两种之一：

• 0 x，表示插入一个大小为 $x$ 的新元素。

• 1 ，表示令集合 $S$ 里所有数加一。

输出格式

输出 $M$ 行，第 $i$ 行表示第 $i$ 次操作结束之后，$S$ 中所有数的 $k$ 次方和。

样例

3 2
0 1
0 1
1

1
2
8

第一次操作后，集合为 $\{1\}$ 。

第二次操作后，集合为 $\{1,1\}$ 。

第三次操作后，集合为 $\{2,2\}$ 。

数据范围

对全部的测试数据，$1\le M \leq 2 \times 10^{5}$，$1\le k \leq 50$，$1\le x\leq 10^5$。

• $10$ 分的数据，$k=1$；
• 对于另外 $20$ 分的数据，$M \leq 3000$；
• 对于另外 $20$ 分的数据，$k=2$；
• 对于另外 $20$ 分的数据，$k=3$；
• 对于另外 $30$ 分的数据，无特殊限制。