题目描述

给定一张 $n$ 个点的有向图 $G=(V,E)$，点的编号为 $1 \sim n$，其每个点都入度、出度均不大于 $1$。

在出度不大于 $1$ 的有向图中，我们记 $f^k(x)$ 表示点 $x$ 在图上沿着出边走 $k$ 步走到的点（如果走到一个不存在出边的点，则停在该点上）。

进一步定义 $G^k=(V,E')$，其中 $E'=\{(x,f^k(x))\mid x\in V\}$。我们称 $G$ 为 $G^k$ 的 $k$ 次方根。

若一个点入度出度均为 $0$ 则称其为孤立点。

又给定一个正整数 $c$，你需要给 $G$ 增加若干条边得到图 $G'$，使得：

1. 每个节点的入度出度均为 $1$。
2. 若两个非孤立点在 $G'$ 上位于同一连通块$^{\dagger}$，则在 $G$ 上也要位于同一连通块。
3. 图 $G'$ 存在 $c$ 次方根。

求加边的方案总数，答案对 $998244353$ 取模。

$^{\dagger}$：本题中定义有向图连通块为：将所有边视作无向边得到的连通块。

输入格式

第一行，两个正整数 $n,c$。

第二行，$n$ 个整数，第 $i$ 个表示点 $i$ 的出边指向的点的编号，若为 $-1$ 则表示无出边。

输出格式

仅一行，一个整数，表示答案对 $998244353$ 取模后的值。

5 4
2 5 -1 -1 -1

3

9 7
7 -1 -1 -1 8 1 -1 -1 5

60

8 10
-1 -1 4 -1 -1 -1 -1 -1

1266

提示

令 $a_i$ 表示点 $i$ 的出边指向点的编号。

【样例解释 #1】

合法的序列 $a_1,\ldots,a_n$ 有：

• $2,5,1,3,4$。
• $2,5,3,4,1$。
• $2,5,4,1,3$。

【数据范围】

本题采用捆绑测试。

子任务编号	$n\le$	$c\le$	特殊性质	分值
1	$5$			$2$
2	$1000$	$2\times10^9$	A	$3$
3	$10$			$15$
4	$20$			$10$
5	$100$			$25$
6	$500$		B	$10$
7				$20$
8	$1000$			$15$

• 特殊性质 A：保证不存在 $a_i=-1$。
• 特殊性质 B：保证所有 $a_i=-1$。

对于 $100\%$ 的数据，保证 $1\le n\le 1000$，$1\le c\le 2\times10^9$，$1\le a_i\le n$ 或 $a_i=-1$，不存在 $i\ne j$ 使得 $a_i=a_j$ 且 $a_i \ne -1$。