Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        dpu = deque()
        start=(inv2, inv2, 0)
        # 葉の場合
        if len(to[u]) == 0:
            dpu.append(start)
            return dpu
        # すべての子をマージ
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        start=(inv2, inv2, 0)
        # 葉の場合
        if len(to[u]) == 0:
            return [deque(start)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            if not dpu:
                dpu = dfs(v)
            else:
                dpv = dfs(v)
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        for d in range(len(dpu)):
            u0, u1, u2 = dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        if not to[u]:
            dp[u].append([inv2, inv2, 0])
            return
        dpu = []
        for v in to[u]:
            dfs(v)
            v = utou[v]
            if not dpu:
                dpu = dp[v]
                utou[u] = v
                continue
            dpv = dp[v]
            if len(dpu) < len(dpv):
                dpu, dpv = dpv, dpu
                utou[u] = v
            for d in range(len(dpv)):
                dpu[d][2] = (dpu[d][2] * sum(dpv[d]) + dpv[d][2] * sum(dpu[d])
                             - dpu[d][2] * dpv[d][2] + dpu[d][1] * dpv[d][1]) % md
                dpu[d][1] = (dpu[d][0] * dpv[d][1] + dpu[d][1] * dpv[d][0]) % md
                dpu[d][0] = (dpu[d][0] * dpv[d][0]) % md
        for d in range(len(dpu)):
            dpu[d][0] = (dpu[d][0] + dpu[d][2]) % md
            dpu[d][2] = 0
        dpu.appendleft([inv2, inv2, 0])

    md = 10 ** 9 + 7
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp):
        i += 1
        to[p].append(i)
    #print(to)
    utou = list(range(n + 1))
    dp = [deque() for _ in range(n + 1)]
    dfs()
    #p2D(dp)
    # print(utou)
    root = utou[0]
    ans = 0
    for dpr in dp[root]:
        ans += dpr[1]
    ans %= md
    print((ans * pow(2, n + 1, md)) % md)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        if not to[u]:
            dp[u] = [[inv2, inv2, 0]]
            return
        dpu = []
        for v in to[u]:
            dfs(v)
            v = utou[v]
            if not dpu:
                dpu = dp[v]
                utou[u] = v
                continue
            dpv = dp[v]
            if len(dpu) < len(dpv):
                dpu, dpv = dpv, dpu
                utou[u] = v
            for d in range(len(dpv)):
                dpu[d][2] = (dpu[d][2] * sum(dpv[d]) + dpv[d][2] * sum(dpu[d])
                             - dpu[d][2] * dpv[d][2] + dpu[d][1] * dpv[d][1]) % md
                dpu[d][1] = (dpu[d][0] * dpv[d][1] + dpu[d][1] * dpv[d][0]) % md
                dpu[d][0] = (dpu[d][0] * dpv[d][0]) % md
        for d in range(len(dpu)):
            dpu[d][0] = (dpu[d][0] + dpu[d][2]) % md
            dpu[d][2] = 0
        dpu.insert(0, [inv2, inv2, 0])

    md = 10 ** 9 + 7
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp):
        i += 1
        to[p].append(i)
    #print(to)
    utou = list(range(n + 1))
    dp = [[] for _ in range(n + 1)]
    dfs()
    #p2D(dp)
    # print(utou)
    root = utou[0]
    ans = 0
    for dpr in dp[root]:
        ans += dpr[1]
    ans %= md
    print((ans * pow(2, n + 1, md)) % md)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Buggy python submission (verdict: Runtime Error):
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        if not to[u]:
            dp[u] = [[0.5, 0.5, 0]]
            return
        dpu = []
        for v in to[u]:
            dfs(v)
            v = utou[v]
            if not dpu:
                dpu = dp[v]
                utou[u] = v
                continue
            dpv = dp[v]
            if len(dpu) < len(dpv):
                dpu, dpv = dpv, dpu
                utou[u] = v
            for d in range(len(dpv)):
                dpu[d][2] = dpu[d][2]*sum(dpv[d])+dpv[d][2]*sum(dpu[d])-dpu[d][2]*dpv[d][2]+dpu[d][1]*dpv[d][1]
                dpu[d][1] = dpu[d][0] * dpv[d][1] + dpu[d][1] * dpv[d][0]
                dpu[d][0] = dpu[d][0] * dpv[d][0]
        for d in range(len(dpu)):
            dpu[d][0] += dpu[d][2]
            dpu[d][2] = 0
        dpu.insert(0, [0.5, 0.5, 0])

    md=10**9+7
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp):
        i += 1
        to[p].append(i)
    #print(to)
    utou = list(range(n + 1))
    dp = [[] for _ in range(n + 1)]
    dfs()
    #p2D(dp)
    #print(utou)
    root=utou[0]
    ans=0
    for dpr in dp[root]:
        ans+=dpr[1]
    print(int(pow(2,n+1)*ans)%md)


main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()