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.