题目描述

本题为「CSP 联测 2021 Day2」数据结构 的数据加强版，与原题唯一不同是 $k$ 的数据范围，且时限为 $1200ms$

维护一个正整数多重集合 $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 300$，$1\le x\leq 10^5$。

请注意代码常数优化，并且在提交选项中勾选 $O2$ 。