덧셈 팰린드롬 수열과 트리

건모는 수열과 팰린드롬을 가지고 놀다가 덧셈 팰린드롬 수열을 만들었다.

수열이 다음 조건을 만족하면 덧셈 팰린드롬 수열이다.

1. 수열에서 인접한 두 수를 고른다.
2. 고른 두 수를 수열에서 지우고, 두 수의 합을 지운 자리에 넣는다.
3. 1번과 2번 과정을 원하는 만큼 반복한다. (반복하지 않아도 된다.)
4. 최종으로 남은 수열의 길이가 $2$ 이상인 팰린드롬 수열이면, 초기 수열은 덧셈 팰린드롬 수열이다.

팰린드롬 수열은 앞에서 읽어도 뒤에서 읽어도 같은 수열이다. 예를 들어 $[11,12,13,12,11]$과 $[11,12,12,11]$은 팰린드롬 수열이지만, $[1,11,111]$과 $[1,12,21,1]$은 팰린드롬 수열이 아니다.

$[1,1,3,5,3,2]$는 $[2,3,5,3,2]$로 만들 수 있으므로 덧셈 팰린드롬 수열이다. $[1,2,5,2]$는 어떤 방식으로 연산해도 길이가 $2$ 이상인 팰린드롬 수열로 만들 수 없으므로 덧셈 팰린드롬 수열이 아니다.

건모는 덧셈 팰린드롬 수열이 너무 쉽다고 생각해서, 포화 이진 트리에서 모든 리프 노드 쌍의 단순 경로 중 덧셈 팰린드롬 수열이 몇 개인지 세어 보려고 한다. 단, $(1,2)$ 쌍과 $(2,1)$ 쌍은 같은 쌍으로 보고 한 번만 센다.

포화 이진 트리는 다음 조건을 만족하는 이진 트리다.

• 모든 노드의 자식은 0개 또는 2개다.
• 모든 리프(자식이 0개인 노드)는 같은 깊이에 있다. 즉, 모든 리프는 루트 노드까지 같은 거리에 있다.

아래 그림은 높이가 $3$인 포화 이진 트리다.

다음과 같이 리프 노드 쌍을 고르면 단순 경로는 $[1,2,1]$이다. 연산을 하지 않아도 이미 팰린드롬 수열이므로 덧셈 팰린드롬 수열이다.

다음과 같이 리프 노드 쌍을 고르면 단순 경로는 $[1,2,1,2,1]$이다. 이 역시 연산을 하지 않아도 이미 팰린드롬 수열이므로 덧셈 팰린드롬 수열이다.

다음과 같이 리프 노드 쌍을 고르면 단순 경로는 $[1,2,2]$이다. 어떤 방식으로 연산해도 길이가 $2$ 이상인 팰린드롬 수열로 만들 수 없으므로 덧셈 팰린드롬 수열이 아니다.

첫째 줄에 트리의 높이 $h$가 주어진다. $(2\le h\le 10)$

둘째 줄에 $A_1$, $A_2$, $\cdots$, $A_{2^h-1}$이 공백으로 구분되어 주어진다. $(-1\,000\le A_i\le 1\,000)$

$A_i$는 $i$번 노드에 쓰인 값이다.

루트 노드는 항상 $1$번이고, $i$번 노드($i\ge 2$)의 부모는 $\lfloor i/2 \rfloor$번 노드다.

입력으로 주어지는 모든 값은 정수다.

첫째 줄에 모든 리프 노드 쌍의 단순 경로 중 덧셈 팰린드롬 수열의 개수를 출력한다.