[GZOI2019]旧词

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1) 
using namespace std;
const int MAX=5e4+5,mod=998244353;
struct p{
	int x,tags;
}s[MAX<<2];
struct q{
	int x,y;
}c[MAX];
struct o{
	int x,y,id;
	bool operator< (const o &a)
	const{
		return x<a.x;
	}
}qu[MAX];
int n,m,num,K,cnt;
int id[MAX],son[MAX],siz[MAX],top[MAX],h[MAX],d[MAX],fa[MAX],dk[MAX],sdk[MAX],ans[MAX],re[MAX];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
int Pow(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
	  if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
void add(int x,int y) {c[++num]=(q){h[x],y},h[x]=num;}
void ADD(int k,int L,int R,int d=1) {s[k].tags+=d,(s[k].x+=1ll*d*((sdk[R]-sdk[L-1]+mod)%mod)%mod)%=mod;}
void pus(int k) {s[k].x=(s[tl].x+s[tr].x)%mod;}
void down(int l,int r,int k) {if(s[k].tags) ADD(tl,l,mid,s[k].tags),ADD(tr,mid+1,r,s[k].tags),s[k].tags=0;}
void change(int l,int r,int k,int L,int R)
{
	if(r<L||R<l) return;
	if(l>=L&&r<=R) return void(ADD(k,l,r));
	down(l,r,k),change(l,mid,tl,L,R),change(mid+1,r,tr,L,R),pus(k);
}
int ask(int l,int r,int k,int L,int R)
{
	if(r<L||R<l) return 0;
	if(l>=L&&r<=R) return s[k].x;
	return down(l,r,k),(ask(l,mid,tl,L,R)+ask(mid+1,r,tr,L,R))%mod;
}
void Upt(int x) {while(x) change(1,n,1,id[top[x]],id[x]),x=fa[top[x]];}
int ask(int x)
{
	int ans=0;
	while(x) (ans+=ask(1,n,1,id[top[x]],id[x]))%=mod,x=fa[top[x]];
	return ans;
}
void dfs(int x=1)
{
	d[x]=d[fa[x]]+(siz[x]=1);
	for(int i=h[x];i;i=c[i].x)
	  {
	  	dfs(c[i].y),siz[x]+=siz[c[i].y];
	  	if(siz[c[i].y]>siz[son[x]]) son[x]=c[i].y;
	  }
}
void dfs1(int x=1,int tp=1)
{
	top[x]=tp,re[id[x]=++cnt]=x;
	if(!son[x]) return;
	dfs1(son[x],tp);
	for(int i=h[x];i;i=c[i].x)
	  if(c[i].y^son[x]) dfs1(c[i].y,c[i].y);
}
int main()
{
	n=read(),m=read(),K=read();
	for(int i=1;i<=n;++i)
	  dk[i]=Pow(i,K);
	for(int i=2;i<=n;++i)
	  add(fa[i]=read(),i);
	dfs(),dfs1();
	for(int i=1;i<=n;++i)
	  sdk[i]=(sdk[i-1]+(dk[d[re[i]]]-dk[d[re[i]]-1]+mod)%mod)%mod;
	for(int i=1;i<=m;++i)
	  qu[i].x=read(),qu[i].y=read(),qu[i].id=i;
	sort(qu+1,qu+1+m);
	for(int i=1,L=1;i<=m;++i)
	  {
	  	while(L<=qu[i].x) Upt(L++);
	  	ans[qu[i].id]=ask(qu[i].y);
	  }
	for(int i=1;i<=m;++i)
	  printf("%d\n",ans[i]);
	return 0;
}