#include<bits/stdc++.h>

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

typedef pair<int,int>pii;

const int N=,mod=;

int n,Q,k,cnt,dep[N],fa[N],pw[N],sz[N],son[N],top[N],id[N],dfx[N];

int ans[N],sum[N<<],val[N<<],lazy[N<<];

vector<int>G[N];

vector<pii>vec[N];

int qpow(int a,int b)

{

    int ret=;

    while(b)

    {

        if(b&)ret=1ll*ret*a%mod;

        a=1ll*a*a%mod,b>>=;

    }

    return ret;

}

void dfs(int u)

{

    dep[u]=dep[fa[u]]+,sz[u]=;

    for(int i=;i<G[u].size();i++)

    if(G[u][i]!=fa[u])

    {

        dfs(G[u][i]),sz[u]+=sz[G[u][i]];

        if(sz[G[u][i]]>sz[son[u]])son[u]=G[u][i];

    }

}

void dfs2(int u,int tp)

{

    top[u]=tp,id[u]=++cnt,dfx[cnt]=u;

    if(son[u])dfs2(son[u],tp);

    for(int i=;i<G[u].size();i++)

    if(G[u][i]!=fa[u]&&G[u][i]!=son[u])dfs2(G[u][i],G[u][i]);

}

void build(int l,int r,int rt)

{

    if(l==r){val[rt]=pw[dep[dfx[l]]];return;}

    int mid=l+r>>;

    build(lson),build(rson);

    val[rt]=(val[rt<<]+val[rt<<|])%mod;

}

void pushdown(int rt)

{

    if(!lazy[rt])return;

    int v=lazy[rt];lazy[rt]=;

    lazy[rt<<]=(lazy[rt<<]+v)%mod,sum[rt<<]=(sum[rt<<]+1ll*v*val[rt<<])%mod;

    lazy[rt<<|]=(lazy[rt<<|]+v)%mod,sum[rt<<|]=(sum[rt<<|]+1ll*v*val[rt<<|])%mod;

}

void update(int L,int R,int l,int r,int rt)

{

    if(L<=l&&r<=R){lazy[rt]++,sum[rt]=(sum[rt]+val[rt])%mod;return;}

    pushdown(rt);

    int mid=l+r>>;

    if(L<=mid)update(L,R,lson);

    if(R>mid)update(L,R,rson);

    sum[rt]=(sum[rt<<]+sum[rt<<|])%mod;

}

void Update(int u)

{

    while(top[u]!=)update(id[top[u]],id[u],,n,),u=fa[top[u]];

    update(,id[u],,n,);

}

int query(int L,int R,int l,int r,int rt)

{

    if(L<=l&&r<=R)return sum[rt];

    pushdown(rt);

    int mid=l+r>>,ret=;

    if(L<=mid)ret=(ret+query(L,R,lson))%mod;

    if(R>mid)ret=(ret+query(L,R,rson))%mod;

    return ret;

}

int Query(int u)

{

    int ret=;

    while(top[u]!=)ret=(ret+query(id[top[u]],id[u],,n,))%mod,u=fa[top[u]];

    ret=(ret+query(,id[u],,n,))%mod;

    return ret;

}

int main()

{

    scanf("%d%d%d",&n,&Q,&k);

    for(int i=;i<=n;i++)pw[i]=(qpow(i,k)-qpow(i-,k)+mod)%mod;

    for(int i=;i<=n;i++)scanf("%d",&fa[i]),G[fa[i]].push_back(i);

    dfs(),dfs2(,);

    build(,n,);

    for(int i=,x,y;i<=Q;i++)scanf("%d%d",&x,&y),vec[x].push_back(pii(y,i));

    for(int i=;i<=n;i++)

    {

        Update(i);

        for(int j=;j<vec[i].size();j++)ans[vec[i][j].second]=Query(vec[i][j].first);

    }

    for(int i=;i<=Q;i++)printf("%d\n",ans[i]);

}