#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back typedef long long ll; using namespace std; const int maxn=2e6+10,mod=998244353; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } int n,q,jc[maxn],jc_inv[maxn],dfn[maxn],pos[maxn],idfn[maxn],top[maxn],fa[maxn],siz[maxn],son[maxn],rnd[maxn],dep[maxn],ct; struct ND { int opt,u; }d[maxn]; vector<int>v[maxn]; void dfs(int u){ siz[u]=1,dep[u]=dep[fa[u]]+1; for(int x:v[u])if(x!=fa[u]){ fa[x]=u;dfs(x);siz[u]+=siz[x]; if(siz[x]>siz[son[u]])son[u]=x; } }void dfs2(int u,int tp){ top[u]=tp,dfn[u]=++ct;idfn[ct]=u,pos[tp]=ct; if(!son[u]) return; dfs2(son[u],tp); for(int x:v[u])if(x!=fa[u]&&x!=son[u])dfs2(x,x); } struct nd { int k,b; nd(){} nd(int _k,int _b){k=_k,b=_b;} }; nd operator+(nd a,nd b){ nd c; c.k=a.k*1ll*b.k%mod; c.b=(a.k*1ll*b.b%mod+a.b)%mod; return c; } struct SegTree { nd T[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void bd(int l,int r,int p){ T[p]=(nd){1,0}; if(l==r)return; int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p)); } void modify(int l,int s,int t,int p,nd x){ if(s==t){T[p]=x;return;} int mid=s+t>>1; if(l<=mid)modify(l,s,mid,ls(p),x);else modify(l,mid+1,t,rs(p),x); T[p]=T[ls(p)]+T[rs(p)]; }nd qry(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return T[p]; int mid=s+t>>1; if(r<=mid)return qry(l,r,s,mid,ls(p)); if(l>mid)return qry(l,r,mid+1,t,rs(p)); return qry(l,r,s,mid,ls(p))+qry(l,r,mid+1,t,rs(p)); } #undef ls #undef rs }Hash; int deg[maxn],endpos[maxn]; int qHash(int u){ nd w=Hash.qry(dfn[u],pos[top[u]],1,n,1); if(deg[endpos[top[u]]])return (w.k+w.b)%mod; return w.b; } struct SGT { struct nd { int mn,lz; }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define mn(p) d[p].mn #define lz(p) d[p].lz void pu(int p){mn(p)=min(mn(ls(p)),mn(rs(p)));} void cl(int p,int x){lz(p)+=x,mn(p)+=x;} void pd(int p){cl(ls(p),lz(p)),cl(rs(p),lz(p)),lz(p)=0;} void modify(int l,int r,int s,int t,int p,int x){if(l>r)return; if(l<=s&&t<=r){cl(p,x);return;}pd(p); int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),x);if(r>=mid+1)modify(l,r,mid+1,t,rs(p),x);pu(p); } void qry(int l,int r,int s,int t,int p,vector<int> &vec){ //cout<<"!! qry "<<l<<" "<<r<<" "<<s<<" "<<t<<endl; if(mn(p)>0)return;pd(p); if(s==t){vec.p_b(son[idfn[s]]);return;}pd(p); int mid=s+t>>1; if(l<=mid)qry(l,r,s,mid,ls(p),vec);if(r>=mid+1)qry(l,r,mid+1,t,rs(p),vec); } #undef ls #undef rs #undef mn #undef lz }Siz; struct BIT { int t[maxn]; int lb(int x){return x&(-x);} void clear(){up(i,1,n)t[i]=1;} void upd(int x,int v){for(;x<=n;x+=lb(x))t[x]=t[x]*1ll*v%mod;} int qry(int x){int res=1;for(;x;x-=lb(x))res=res*1ll*t[x]%mod;return res;} int g(int l,int r){int A=qry(r),B=qry(l-1);return A*1ll*qp(B,mod-2)%mod;} }Tree; ll hsh[maxn],qwq[maxn]; int vis[maxn]; vector<int>vec; void qry(int u){ //cout<<"! qry"<<endl; while(u)Siz.qry(dfn[top[u]],dfn[u],1,n,1,vec),u=fa[top[u]]; //cout<<"! qry"<<endl; } void modify_siz(int u){ while(u){ Siz.modify(dfn[u],dfn[u],1,n,1,-1); Siz.modify(dfn[top[u]],dfn[u]-1,1,n,1,1); u=fa[top[u]]; } } void get_pos(int u){ vec.clear();modify_siz(u); qry(u); } void modify_hash(int u){ //cout<<"modify_hash "<<u<<endl; int tmp=u; while(tmp){ qwq[top[tmp]]=qHash(top[tmp]);if(top[tmp]!=1)hsh[fa[top[tmp]]]=qHash(top[tmp]); tmp=fa[top[tmp]]; } while(u){ Hash.modify(dfn[u],1,n,1,nd(hsh[u]*1ll*rnd[dep[u]]%mod,rnd[dep[u]])); if(fa[top[u]]){ hsh[fa[top[u]]]=hsh[fa[top[u]]]*1ll*qp(qwq[top[u]],mod-2)%mod*1ll*qHash(top[u])%mod; }u=fa[top[u]]; } //cout<<"! "<<qHash(8)<<endl; } map<int,int>mp[maxn]; void upd(int u,int sgn){ int h=qHash(u); int x=mp[fa[u]][h]+(vis[son[fa[u]]]&&qHash(son[fa[u]])==h); //cout<<"! "<<u<<" "<<h<<" "<<x<<" "<<sgn<<endl; Tree.upd(dfn[fa[u]],jc_inv[x]*1ll*jc[x+sgn]%mod); if(u!=son[fa[u]])mp[fa[u]][h]+=sgn; } void ins(int u){ ++deg[fa[u]],endpos[top[u]]=u; //cout<<"son1 "<<son[1]<<endl; //cout<<"ins "<<u<<endl; //get_pos(fa[u]);cout<<"getpos"<<endl; //for(int x:vec)cout<<"test "<<x<<endl; for(int x:vec)if(x!=u)upd(x,-1),vis[x]=0; modify_hash(u);upd(u,1);vis[u]=1; for(int x:vec)if(x!=u)upd(x,1),vis[x]=1; } int qry_ans(int u){ return Tree.g(dfn[u],dfn[u]+siz[u]-1); } void slv(){ q=read();n=1; up(i,1,q){ d[i].opt=read(),d[i].u=read(); if(!d[i].opt)v[d[i].u].p_b(++n); } up(i,1,n)hsh[i]=1; mt19937_64 rng(0); up(i,1,n)rnd[i]=rng()%mod; jc[0]=jc_inv[0]=1; up(i,1,n)jc[i]=jc[i-1]*1ll*i%mod,jc_inv[i]=qp(jc[i],mod-2); dfs(1),dfs2(1,1);endpos[1]=1; Hash.bd(1,n,1); Tree.clear(); Siz.modify(1,1,1,n,1,-1); Hash.modify(1,1,n,1,nd(rnd[1],rnd[1])); vis[1]=1; int pos=1; up(i,1,q){ int opt=d[i].opt,u=d[i].u; if(!opt)ins(++pos); else printf("%lld\n",qry_ans(u)); //cout<<"??? "<<qry_ans(1)<<" "<<qHash(8)<<" "<<son[8]<<endl; } } int main(){ //freopen("1.in","r",stdin),freopen("1.out","w",stdout); //int t=read();while(t--)slv(); slv(); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }