만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

트리

면접 대비

시간 제한2초메모리 제한1024 MB

요약
루트가 있는 트리의 간선을 빨강과 초록으로 칠하는 방법 중, 각 정점의 자식 간선 가운데 빨간 간선이 최대 하나인 경우의 수를 10^9 + 7로 나눈 나머지로 구합니다.
난이도

보통10점 중 4점

유형
트리, 동적 계획법
정답자
아직 제출이 없습니다

문제

작은 왕국에 한 화가가 살고 있다. 그는 재능이 뛰어나서 자유 시간 대부분을 그림 그리는 데 쓴다. 특히 나무를 잘 그린다. 여왕은 그의 그림을 무척 좋아해서 나무 그림 한 점을 자기 방에 걸어 두었다.

곧 그림 전시회가 열린다는 소식이 왕국에 전해졌다. 다른 왕국의 왕과 여왕들은 재능 있는 화가가 있는 나라를 높이 평가하고, 서로의 성을 자주 방문하며 긴밀히 협력한다. 그래서 여왕은 화가의 작품 한 점을 전시회에 보내기로 했다. 왕국이 작아서 화가는 컬러 물감을 살 수 없었고, 그의 그림은 항상 흑백이었다. 여왕은 자기 왕국의 그림이 전시회에서 눈에 띄기를 바랐고, 궁중 약사에게 왕국 국기의 색인 빨강과 초록 두 가지 물감을 만들라고 명령했다. 물감이 준비되자 화가는 다른 문제에 관심을 갖게 되었다. 나무를 어떻게 칠할 것인가 하는 문제였다.

화가는 나무의 각 간선마다 두 색 중 하나를 고르고, 그 간선을 그 색으로 칠한다. 여왕은 흥미롭게 칠해진 나무만 좋아한다. 칠하기가 흥미롭다는 것은, 모든 정점에 대해 그 정점의 자식들에서 그 정점으로 들어오는 빨간 간선이 최대 하나뿐이라는 뜻이다.

화가는 벌을 받지 않으려고 나무를 흥미롭게 칠하려 한다. 하지만 같은 나무라도 칠하는 방법이 여러 가지이고, 그는 고르기 어려워한다. 흥미로운 칠하기가 몇 가지인지 세어 화가를 도와 달라.

경우의 수가 클 수 있으므로 109+710^9 + 7로 나눈 나머지를 출력한다.

입력

첫째 줄에 트리의 정점 개수 nn (1≤n≤1041 \le n \le 10^4)이 주어진다.

둘째 줄에는 n−1n - 1개의 정수가 주어진다. ii번째 정수는 정점 ii의 부모인 pip_i이다. 루트의 번호는 항상 0이다.

출력

흥미로운 칠하기의 개수를 109+710^9 + 7로 나눈 나머지를 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    5
    0 1 0 2
    
    예상 출력
    12
    
  2. 예제 2

    입력
    1
    
    예상 출력
    1