32872번 - 덧셈 팰린드롬 수열과 트리

문제

건모는 수열과 팰린드롬을 가지고 놀다가, 덧셈 팰린드롬 수열을 개발했다.

덧셈 팰린드롬 수열은 다음 조건을 만족하는 수열을 뜻한다.

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)$번째 노드의 부모는 $\left\lfloor \frac{i}{2} \right\rfloor$이다.

입력으로 주어진 모든 값은 정수이다.

출력

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

제한

힌트