Submission #2708410

---

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]:
        R.append(Q[j])

    if R:
        R.sort(key=len, reverse=1)

        # dequeの小さい方から大きい方へマージする処理
        last = R.pop()
        while R:
            nxt = R.pop()
            for k in range(len(last)):
                a0, a1, a2, c0 = last.popleft()
                b0, b1, b2, c1 = nxt[k]
                nxt[k] = [a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD, c0+c1]
            last = nxt
        # a0 <- a2
        for e in last:
            e[0] += e[2]
            e[2] = 0
        q.extend(last)
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