Completing a Directed Graph to a Permutation with a c-th Root

You are given a directed graph \(G=(V,E)\) with \(n\) vertices numbered from \(1\) to \(n\). In \(G\) every vertex has in‐degree and out‐degree at most \(1\). For any vertex \(x\) and positive integer \(k\), we define \(f^k(x)\) as the vertex reached by following the unique outgoing edge \(k\) times (if at some step there is no outgoing edge, remain at that vertex). Define \(G^k=(V,E')\) with \(E' = \{ (x, f^k(x)) : x\in V \}\). We say that \(G\) is a \(k\)th root of \(G^k\).

A vertex with both in‐degree and out‐degree equal to \(0\) is called isolated.

You are also given a positive integer \(c\). You must add some extra edges to \(G\) (i.e. only add, never remove) to obtain a new graph \(G'\) satisfying the following conditions:

1. Every vertex has in‐degree exactly \(1\) and out‐degree exactly \(1\) (that is, \(G'\) is a permutation on \(n\) vertices).
2. If two non–isolated vertices lie in the same connected component (where connectivity means that all edges are regarded as undirected) of \(G'\), then they must already lie in the same connected component of \(G\).
3. The permutation \(G'\) has a \(c\)th root, i.e. there exists a directed graph \(H\) with every vertex having in‐degree and out‐degree \(1\) such that \(H^c = G'\). A known necessary and sufficient condition is that in the cycle decomposition of \(G'\), for each cycle of length \(L\) the total number of \(L\text{-cycles}\) is divisible by \(\gcd(L,c)\).

Your task is to count the number of ways to add edges to \(G\) (without removing any original edge) so that all the above conditions are met. Since the answer might be huge, output it modulo \(998244353\).

Note on the Input: The graph \(G\) is given by specifying, for each vertex \(1 \le i \le n\), the index of the vertex that \(i\) points to. A value of \(0\) indicates that \(i\) has no outgoing edge in \(G\).

inputFormat

The first line contains two integers \(n\) and \(c\) \((1 \le n \le \text{small limit},\; 1 \le c \le 10^9)\).

The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) where \(a_i\) is either \(0\) (meaning no edge from \(i\)) or an integer in \([1,n]\) indicating a directed edge from vertex \(i\) to vertex \(a_i\). It is guaranteed that for every vertex, its in–degree and out–degree do not exceed \(1\).

outputFormat

Output a single integer, the number of ways to add edges so that the resulting graph \(G'\) satisfies the conditions, modulo \(998244353\).

sample

3 2
0 0 0

3