你决定设计你自己的软件包管理器。如果软件包 A 依赖软件包 B ，那么安装软件包 A 以前，必须先安装软件包 B 。同时，如果想要卸载软件包 B ，则必须卸载软件包 A 。现在你已经获得了所有的软件包之间的依赖关系。除 $0$ 号软件包以外，所有软件包都会依赖一个且仅一个软件包，而 $0$ 号软件包不依赖任何一个软件包。依赖关系不存在环。

现在有一些安装或卸载软件包的操作，需要求出这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包）。

给定一个字符串 $S$ ，求出 $num$ 数组——对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $num[i]$ 。

特别地，为了避免大量的输出，你不需要输出 $num[i]$ 分别是多少，你只需要输出所有 $(num[i]+1)$ 的乘积，对 ${10}^9+7$ 取模的结果即可。

维护一个数列，给定初始的 $n$ 个数字。

现有六种命令：

• 在第 $pos$ 个数后插入 $tot$ 个数
• 翻转从第 $pos$ 个数开始的 $tot$ 个数
• 删除从第 $pos$ 个数开始的 $tot$ 个数
• 查询从第 $pos$ 个数开始的 $tot$ 个数的和
• 设定从第 $pos$ 个数开始的 $tot$ 个数设定为 $c$
• 查询整个数列中和最大的连续子区间的和

初始时，第 $i$ 号战舰处于第 $i$ 列 $(i=1,2,\dots ,30000)$ 。

有两种指令：

合并指令为 M i j ，含义为将第 $i$ 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 $j$ 号战舰所在的战舰队列的尾部。

询问指令为 C i j 。该指令意思询问第 $i$ 号战舰与第 $j$ 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

维护一个数列。

现有四种命令，新加入一个数 $k$ ，把每个数加上 $k$ ，把每个数减去 $k$ ，查询第 $k$ 大的数。如果数列中的任意数小于 $min$ ，将它立即删除。并在最后输出总共删去的数的个数 $res$ 。

如果新加入的数 $k$ 的初值小于 $min$ ，它将不会被加入数列。