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.