#include #include const int N=214514,D=100; int n,m,mod; int a[N]; int tag[N][D],fa[N]; std::vector e[N]; void dfs(int u,int f=0) { fa[u]=f; for(int v:e[u])if(v!=f)dfs(v,u); } int main() { scanf("%d %d",&n,&mod); int u,v; for(int i=1;i=0&&x) { tag[x][d]=1ll*tag[x][d]*w%mod; if(d>=1)tag[x][d-1]=1ll*tag[x][d-1]*w%mod; if(x==1) // ?????????????????? { for(int i=0;i<=d-2;i++)tag[1][i]=1ll*tag[1][i]*w%mod; break; } x=fa[x]; d--; } } else { int ans=a[x]; for(d=0;d<=40;d++) // ????? tag { if(!x)break; ans=1ll*ans*tag[x][d]%mod; x=fa[x]; } printf("%d\n",ans); } } return 0; }