题目描述

在一个神秘的数字王国里，存在着一个名为多重集合 $S$ 的神奇宝箱。这个宝箱最初是空的。王国的法则规定，探险者们可以通过两种神奇的操作来改变这个宝箱的内容。

首先，探险者们可以进行插入操作，将一个新的非负整数 $x$ 放入宝箱中。

其次，探险者们还可以进行修改操作，让宝箱中所有的数字都同时增加 1。

每当探险者完成一次操作后，宝箱便会发出神秘的光芒，要求他们计算集合 $S$ 中所有数字的 $k$次方和，$k$是王国的智者们预先设定的一个神秘数字。

输入格式

第一行输入两个数$M,k$

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

0 x ，表示插入操作。

1 ，表示修改操作。

输出格式

输出 $M$ 行数，第 $i$ 行表示第 $i$ 次操作结束之后，宝箱 $S$ 中所有数的 $k$ 次方和。答案可能会很大，你需要对$10^9+7$取模。

样例

样例1

3 2
0 1
0 1
1

1
2
8

样例解释：

第一次操作后，宝箱集合为 1 。

第二次操作后，宝箱集合为 1 1 。

第三次操作后，宝箱集合为 2 2 。

样例2

见下发文件

数据范围

对全部的测试数据$M\le 2\times 10^5,1\le k\le 50$, $0\le x\le 10^5$

10 分的数据,$k=1$；

20 分的数据,$M\le 3000$

20 分的数据，$k=2$

20 分的数据，$k=3$

30 分的数据，无特殊限制