题目背景

普通多项式的系数可以是任意整数，而在二进制多项式中，所有系数都只能是 $0$ 或 $1$，并且加法、乘法中的系数运算均在模 $2$ 意义下进行。

这使得许多在普通多项式中十分庞大的系数会自动消去。现在给定一个二进制多项式以及一个很大的幂次，请求出其幂中某一项的系数。

题目描述

一个次数为 $n$ 的二进制多项式 $P$ 由 $n+1$ 个系数：

$$a_0,a_1,\ldots,a_n$$

确定，其中：

• 每个 $a_i$ 都是 $0$ 或 $1$；
• $a_n=1$。

多项式为：

$$P(x)=a_0x^0+a_1x^1+\cdots+a_nx^n.$$

二进制多项式的加法和乘法与普通多项式相同，但所有系数都需要对 $2$ 取模。

例如：

$$(x+x^3)(1+x^2) =x+2x^3+x^5 \equiv x+x^5\pmod 2.$$

因此，二进制多项式的每个系数始终只可能是 $0$ 或 $1$。

给定正整数 $m$ 和非负整数 $k$，请计算二进制多项式：

$$P(x)^m$$

中 $x^k$ 项的系数。

输入格式

第一行包含一个整数 $n$，表示多项式 $P$ 的次数。

第二行包含 $n+1$ 个整数：

$$a_0,a_1,\ldots,a_n.$$

第三行包含两个整数 $m,k$。

输出格式

输出一个整数，表示二进制多项式 $P(x)^m$ 中 $x^k$ 项的系数。

答案一定是 0 或 1。

数据范围

对于所有测试数据：

• $0\le n\le 49$；
• $a_i\in\{0,1\}$；
• $a_n=1$；
• $1\le m\le 10^{16}$；
• $0\le k\le n\cdot m$。

所有输入整数均可使用有符号 $64$ 位整数表示。

样例 1

输入

2
1 0 1
3 4

输出

1

解释

此时：

$$P(x)=1+x^2.$$

在模 $2$ 意义下：

$$\begin{aligned} P(x)^3 &=(1+x^2)^3\\ &=1+3x^2+3x^4+x^6\\ &\equiv 1+x^2+x^4+x^6\pmod 2. \end{aligned}$$

因此，$x^4$ 项的系数为 $1$。

样例 2

输入

2
1 0 1
3 5

输出

0

解释

与样例 1 相同：

$$P(x)^3=1+x^2+x^4+x^6.$$

其中不存在 $x^5$ 项，因此其系数为 $0$。

样例 3

输入

5
0 0 1 1 0 1
7 15

输出

1

样例 4

输入

0
1
1 0

输出

1

解释

此时：

$$P(x)=1,$$

因此：

$$P(x)^1=1,$$

常数项的系数为 $1$。