23648번 - Polynomial 다국어

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.

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