Submission #2708419

---

Source Code Expand

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
for i in range(N, -1, -1):
    # i+1 <- P[i]
    Q[i] = q = deque([[1, 1, 0, 1]])

    # 子ノードのdequeを集める
    R = []
    for j in G[i]:
        S = Q[j]
        if not R:
            R = S
            continue

        # |R| > |S|
        if len(R) < len(S):
            R, S = S, R

        # dequeの小さい方から大きい方へマージする処理
        for k in range(len(S)):
            a0, a1, a2, c0 = S.popleft()
            b0, b1, b2, c1 = R[k]
            R[k] = [a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD, c0+c1]
    # a0 <- a2
    for e in R:
        e[0] += e[2]
        e[2] = 0
    q.extend(R)
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission Info

Judge Result