题目还是很不错的。
我们对于每一个 \(i\)，直接对 \(a_i\) 向 \(i\) 连一条边，很容易发现这是一个基环树。
那我们直接按照套路来，考虑一个环对答案的贡献，显然环如果合法，则所有颜色相同，直接把它看成一个点即可。
缩点后那剩下的解释一棵树了，我们考虑 dp，设 \(dp_{u,j}\) 表示以 \(u\) 为根，\(u\) 的颜色为 \(j\) 时的方案数。
那么又转移
这个十分的经典，设
\[f_{u,j}=\sum_{i=1}^{j}dp_{v,i} \]转移式子就是
\[ dp_{u,j} = \prod_{v\in son(u)}f_{u,j} \]就是前缀和优化 dp 了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2055,mod=998244353,INF=1e18;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define qmi(a,b) a=min(a,b)
#define qma(a,b) a=max(a,b)
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define atrep(i,l,r) for(int i=(r);i>=(l);i--)
#define vec vector<int>
#define pb push_back
namespace fast_IO {
#define IOSIZE 100000
char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
inline void print(char x) { putchar(x); }
inline void print(char *x) { while (*x) putchar(*x++); }
inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
inline void print(bool b) { putchar(b+48); }
template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
struct EDGE{
int idx=0;
int h[N*2];
struct temple{
int nxt,v;
}g[N*2];
void add(int a,int b){
g[++idx].nxt=h[a],g[idx].v=b,h[a]=idx;
}
}G,T;
int dfn[N],low[N],stk[N],top,timetamp,col[N],scc_cnt=0,n,m;
bool in_sta[N];
void tarjan(int u){
dfn[u]=low[u]=++timetamp;
stk[++top]=u,in_sta[u]=1;
for(int i=G.h[u];i;i=G.g[i].nxt){
int v=G.g[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(in_sta[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++scc_cnt;
int y;
do{
y=stk[top--];
col[y]=scc_cnt;
in_sta[y]=0;
}while(y!=u);
}
}
int dp[N][N],f[N][N];
bool vst[N];
void df5(int u,int fa){
vst[u]=1;
rep(i,1,m) dp[u][i]=1,f[u][i]=i;
for(int i=T.h[u];i;i=T.g[i].nxt){
int v=T.g[i].v;
if(v==fa||vst[v]) continue;
df5(v,u);
rep(l,1,m){
dp[u][l]*=f[v][l];
f[u][l]=f[u][l-1]+dp[u][l];
dp[u][l]%=mod;
f[u][l]%=mod;
}
}
}
int inn[N];
signed main(){
cin>>n>>m;
rep(i,1,n){
int fa;
cin>>fa;
G.add(fa,i);
}
int ans=1;
rep(i,1,n){
if(dfn[i]) continue;
tarjan(i);
}
rep(u,1,n){
for(int j=G.h[u];j;j=G.g[j].nxt){
int v=G.g[j].v;
if(col[v]!=col[u]){
T.add(col[u],col[v]);
inn[col[v]]++;
// cout<<col[u]<<" "<<col[v]<<endl;
}
}
}
rep(i,1,scc_cnt){
if(inn[i]!=0) continue;
df5(i,0);
ans=ans*f[i][m];
ans%=mod;
// cout<<f[i][m]<<endl;
}
cout<<ans%mod<<endl;
}