레드-블랙 트리

여러 프로그래밍 언어의 표준 라이브러리에서 균형 잡힌 트리를 구현할 때 레드-블랙 트리를 흔히 사용한다. 이 문제에서는 주어진 모양의 레드-블랙 트리의 개수를 세려고 한다.

이진 트리는 정점들을 트리 모양으로 배치한 것이다. 각 정점은 자식을 최대 둘 가지며, 하나는 왼쪽, 다른 하나는 오른쪽이라고 부른다. 왼쪽 자식과 오른쪽 자식은 각각 없을 수도 있고 둘 다 없을 수도 있다.

정점 $Y$가 정점 $X$의 자식이면, 정점 $X$를 정점 $Y$의 부모라고 한다. 트리의 모든 정점은 루트를 제외하면 부모가 정확히 하나 있다. 부모가 없는 유일한 정점을 트리의 루트라고 한다.

루트를 제외한 각 정점을 부모와 연결하자. 그러면 각 정점마다 루트에서 그 정점으로 가는 경로가 정확히 하나 존재한다.

이진 트리의 모든 정점을 빨간색 또는 검은색으로 칠했을 때 다음 조건을 모두 만족하면 그 트리를 레드-블랙 트리라고 한다.

1. 빨간 정점의 부모는 검은색이다.
2. 루트에서 자식이 하나 이상 없는 정점까지 가는 경로에 있는 검은 정점의 수가 모두 같다.

두 가지 색으로 정점을 칠한 이진 트리의 예가 다음 그림에 나와 있다.

(а)	(б)	(в)

칠해진 정점을 검은색, 칠해지지 않은 정점을 빨간색으로 보면 그림 (а)의 트리는 레드-블랙 트리이고 그림 (б)와 (в)의 트리는 아니다. 그림 (б)의 트리에서는 첫 번째 조건이 깨진다. 빨간 정점 5의 부모 2도 빨간색이다. 그림 (в)의 트리에서는 두 번째 조건이 깨진다. 루트에서 정점 1까지 가는 경로에는 검은 정점이 하나뿐이지만, 예를 들어 루트에서 정점 3까지 가는 경로에는 둘이다.

주어진 이진 트리에 대해 정점을 검은색과 빨간색으로 칠해 레드-블랙 트리로 만드는 방법의 수를 구하시오.

첫째 줄에 트리의 정점 수 $n$이 주어진다 ($1 \le n \le 1000$).

트리의 정점에는 $1$부터 $n$까지 번호가 붙어 있다. 다음 $n$개 줄에 각 정점의 왼쪽 자식과 오른쪽 자식 번호가 하나씩 주어진다. 자식이 없으면 그 번호 대신 0이 주어진다. 입력은 올바르며, 주어진 수들이 실제로 이진 트리를 이룬다고 보장된다.

입력으로 주어진 이진 트리의 정점을 빨간색과 검은색으로 칠해 레드-블랙 트리로 만드는 방법의 수를 한 줄에 출력한다.

첫 번째 예제의 트리에서 가능한 모든 색칠 방법이 다음 그림에 나와 있다.