You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

根据 这题 我们知道了两个排列可以进行运算。这次我们要采用这里的运算了。虽然我不会这么定义。

给出排列 $p$ 和非负整数 $k$。我们定义置换函数 $f_k(x)$：

即 $x$ 在排列 $p$ 上置换 $k$ 次的结果。

对于一棵树 $T$，如果对于它任意一条边 $(x,y)\in T$，都有置换后的边 $(f_k(x),f_k(y))\in T$，那么称这棵树为排列的置换树。

求此排列的置换树的个数，对 $998\ 244\ 353$ 取模。

输入格式

第一行输入两个整数 $n,k$。

第二行输入 $n$ 个正整数表示排列。

输出格式

输出一个整数表示答案对 $998\ 244\ 353$ 取模后的结果。

5 2
2 3 4 1 5

5

15 1
1 3 2 5 6 7 4 9 10 11 12 13 14 15 8

21

5 0
1 2 3 4 5

125

提示

样例解释 1

以下五棵树可行：

$T=\{(1,2),(3,4),(1,5),(3,5)\}$

$T=\{(1,2),(3,4),(2,5),(4,5)\}$

$T=\{(1,4),(3,2),(1,5),(3,5)\}$

$T=\{(1,4),(3,2),(2,5),(4,5)\}$

$T=\{(1,5),(2,5),(3,5),(4,5)\}$

样例解释 3

我们发现 $k=0$ 就是数树。凯莱公式套一套就行了。

数据范围

本题采用捆绑测试。

$3\le n\le 2\cdot10^6$，$0\le k\le10^{18}$。

• Subtask 1：$k=0$。共 $1$ 分。
• Subtask 2：$n\le 8$。共 $14$ 分。
• Subtask 3：$k=1$，$n\le 300$。共 $30$ 分。
• Subtask 4：$k=1$。共 $15$ 分。
• Subtask 5：$n\le 2000$。共 $15$ 分。
• Subtask 6：无特殊限制。共 $25$ 分。

本题输入量巨大，但出题人不加快读也随便过。