题目描述

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

• 插入：插入一个新数$x$ $(x\leq 100000)$

• 修改：令集合中所有数加 $1$

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

和可能很大，你只需要输出它对$1e9+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$ 。

大数据

限制条件

对全部的测试数据, $M \leq 2 \times 10^{5}, k \leq 50$.

• $10$ 分的数据, $k=1$;

• $20$ 分的数据, $M \leq 3000$;

• $20$ 分的数据, $k=2$;

• $20$ 分的数据, $k=3$;

• $30$ 分的数据, 无特殊限制。