이길 수 있는 구간

정수 $M$과, $0, 1, 2, \dots, 2^M - 1$을 한 번씩 담은 길이 $2^M$의 배열 $A$가 주어진다.

컴퓨터가 $A$에서 비어 있지 않은 연속한 구간 하나를 고른다. 그 뒤 당신은 서로 다른 두 위치를 골라 그 위치에 있는 두 수를 교환해야 한다. 교환은 반드시 한 번 해야 하고, 고른 두 위치는 구간 안에 있어도 되고 밖에 있어도 되며 한쪽씩 있어도 된다. 교환을 마친 뒤 컴퓨터가 고른 구간 안의 수를 모두 비트 XOR 한 값이 정확히 $2^M - 1$이면 당신이 이긴다.

컴퓨터가 고를 수 있는 구간은 $\frac{2^M(2^M+1)}{2}$개다. 그중 당신이 이길 수 있는 구간이 몇 개인지 구하여라.

첫째 줄에 정수 $M$ ($1 \le M \le 20$)이 주어진다.

둘째 줄에 배열 $A$를 이루는 $2^M$개의 수가 공백으로 구분되어 주어진다. 이 수는 $0, 1, 2, \dots, 2^M - 1$의 순열이다.

당신이 이길 수 있는 구간의 개수를 한 줄에 출력한다.

첫 번째 예제에서 컴퓨터가 구간 1 2 3을 고르면 당신은 0과 3을 교환해서 이긴다. 이 예제에서는 배열 전체를 고른 경우를 빼면 어떤 구간을 골라도 이길 수 있다.

두 번째 예제에서 컴퓨터가 배열 전체 3 7 0 4 6 1 5 2를 고르면, 어떤 두 수를 교환해도 구간의 XOR 값 0은 그대로다.