시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 256 MB32266.667%

문제

Given a polynomial $P$ with coefficients from $\{0, 1\}$, print the number of odd coefficients in its $n$-th power.

입력

The first line contains an integer $d$ ($1 \le d \le 20$) --- the degree of the polynomial.

The second line contains $d+1$ integers $a_i$ ($a_i \in \{0, 1\}$), denoting the coefficients of $P$ from lowest to greatest.

The third line contains an integer $n$ ($1 \le n \le 10^{16}$).

출력

Print the answer to the problem in the only line.

예제 입력 1

1
1 1
3

예제 출력 1

4

예제 입력 2

5
0 1 1 0 1 1
3

예제 출력 2

10

노트

In the first sample test $P(x)^3 = 1 + 3x + 3x^2 + x^3$, having all 4 coefficients odd.