1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
| #include<bits/stdc++.h> using namespace std; typedef long long ll;
ll ny[100001]; const ll mod=1e9+7;
struct F { ll a,b,c; inline ll val(ll x,ll y){return (a*x+b*y+c)%mod;} }f[100001][2]; F operator + (F f1,F f2) { f1.a=(f1.a+f2.a)%mod,f1.b=(f1.b+f2.b)%mod,f1.c=(f1.c+f2.c)%mod; return f1; } F operator - (F f1,F f2) { f1.a=f1.a-f2.a,f1.b=f1.b-f2.b,f1.c=f1.c-f2.c; f1.a=(f1.a+mod)%mod;f1.b=(f1.b+mod)%mod;f1.c=(f1.c+mod)%mod; return f1; } F operator + (F _,ll x) { _.c=(_.c+x)%mod; return _; } F operator - (F _,ll x) { _.c=((_.c-x)%mod+mod)%mod; return _; } F operator * (ll x,F _) { _.a=_.a*x%mod,_.b=_.b*x%mod,_.c=_.c*x%mod; return _; } F operator / (F _,ll x) { x=ny[x],_.a=_.a*x%mod,_.b=_.b*x%mod,_.c=_.c*x%mod; return _; }
ll qkp(ll x,ll y) { ll ret=1LL,_=x; while(y) { if(y&1)ret=ret*_%mod; y>>=1; _=_*_%mod; } return ret; }
char mp[100000];ll dis[100001],n,fa[100001]; vector <ll> son[100001]; ll sz[100001];
void dfs(ll x) { sz[x]=1; for(ll i:son[x]) { dfs(i); sz[x]+=sz[i]; dis[x]+=dis[i]+sz[i]; } } void dfs2(ll x) { for(ll i:son[x]) { dis[i]+=dis[x]-dis[i]+n-(sz[i]<<1); dfs2(i); } } bool ntpr[100001];ll pr[100001],tnc=0; int main() { freopen("c.in","r",stdin); freopen("c.out","w",stdout); scanf("%lld",&n); scanf("%s",mp); ll cnt=0; for(int i=0;i<n;i++)cnt+=(mp[i]=='1'); for(ll i=2;i<=n;i++)scanf("%lld",&fa[i]),son[fa[i]].push_back(i); dfs(1LL); dfs2(1LL); ny[1]=1; for(ll i=2;i<=n;i++) { if(!ntpr[i])pr[++tnc]=i,ny[i]=qkp(i,mod-2); for(int j=1;j<=tnc&&pr[j]*i<=n;j++) { ny[pr[j]*i]=ny[i]*ny[pr[j]]%mod; ntpr[pr[j]*i]=1; if(!i%pr[j])break; } } for(int i=1;i<=n;i++)dis[i]=dis[i]%mod*ny[n]%mod; f[1][0].a=1LL,f[1][1].b=1LL; for(ll i=2;i<n;i++) { f[i][1]=(n*f[i-1][1]-(ll)(i>2LL)-f[i-2][0]-(i-2)*f[i-2][1])/(n-i+1); f[i][0]=n*f[i-1][0]-1LL-(i-1)*f[i-2][0]; f[i][0]=(f[i][0]-f[i][1])/(n-i); } ll s1,s2,s3,s4,s5,s6; s1=(f[n-1][0]-(n-1)*f[n-2][0]/n).a; s2=(f[n-1][0]-(n-1)*f[n-2][0]/n).b; s3=(f[n-1][0]-(n-1)*f[n-2][0]/n).c; s4=(f[n-1][1]-(n-2)*f[n-2][1]/n-f[n-2][0]/n-ny[n]).a; s5=(f[n-1][1]-(n-2)*f[n-2][1]/n-f[n-2][0]/n-ny[n]).b; s6=(f[n-1][1]-(n-2)*f[n-2][1]/n-f[n-2][0]/n-ny[n]).c; ll x,y; s2*=s4,s2-=s1*s5,s2%=mod,s2+=mod,s2%=mod,s3*=s4,s3-=s1*s6,s3%=mod,s3+=mod,s3%=mod; y=s3*qkp(s2,mod-2)%mod,y=(mod-y)%mod; s6=mod-(s6+s5*y)%mod; s6%=mod; x=s6*qkp(s4,mod-2)%mod; ll a[2]; a[0]=f[cnt][0].val(x,y),a[1]=f[cnt][1].val(x,y); a[0]+=ny[n],a[0]%=mod,a[1]+=ny[n],a[1]%=mod; ll ans=0; for(int i=0;i<n;i++) { if(mp[i]=='1')ans=(ans+a[1]*dis[i+1])%mod; else ans=(ans+a[0]*dis[i+1])%mod; } printf("%lld",ans); return 0; }
|