你一定了解 ACM 题目中的圆圈游戏，例如约瑟夫环问题。今天我们要介绍一种新的圆圈游戏，描述如下：有一个圆圈，包含 $M$ 个点，编号从 $0$ 到 $M-1$。起初，$n$ 名学生站在圆圈的不同点上。多名学生站在同一个点上是有可能的。每一秒，每名学生都会沿顺时针方向移动一步。下图给出了一个 $M=8$ 且 $n=3$ 的例子。最初，第一名学生 $S_1$ 站在点 $0$，第二名学生 $S_2$ 站在点 $2$，第三名学生站在点 $7$。2 秒后，他们会改变位置，如下图右侧所示。

在游戏开始时，Tracy 记下了所有学生的位置。然后他去睡觉，学生们会遵守上述规则继续游戏，直到 Tracy 醒来。一段时间后，Tracy 醒了。他发现很难确定第一名学生 $S_1$ 站在哪里，第二名学生 $S_2$ 站在哪里，以此类推，因为所有学生都完全相同且无法区分。因此，Tracy 记录了所有学生的位置，并写下了这些位置的异或和（数组 $A$ 的异或和是指 $A[0] \oplus A[1] \oplus \dots \oplus A[n-2] \oplus A[n-1]$，其中 $\oplus$ 是异或运算，例如 $0111 \oplus 1011 = 1100$）。现在 Tracy 想请你帮他算出他睡了多少秒。为了简化问题，点的数量总是 $2$ 的幂，即 $2^m$。

此外，Tracy 知道他睡觉的时间不超过 $T$。请注意，Tracy 睡觉的时间必须大于零。可能存在多个不同的时间段满足上述条件。

输入格式

输入包含多组测试数据。每组测试数据首先包含四个整数 $n, m, S, T$。$S$ 是 Tracy 醒来时学生位置的异或和。$n, m, T$ 的含义如上所述。接下来一行包含 $n$ 个整数，表示学生最初的位置。输入以文件结束符（EOF）结束。

$0 < n \le 100000, 0 < m \le 50, 0 \le S < 2^{50}, 0 < T \le 10^{16}$，且学生位置在范围 $[0, 2^m)$ 内。

输出格式

对于每组测试数据，输出 Tracy 睡觉的可能时间段数量，且这些时间段需满足上述限制。如果没有匹配的时间，请输出零。

样例

输入 1

3 3 7 5
0 2 7
5 3 7 5
1 2 3 4 5
4 4 0 10
1 3 5 7
6 5 18 100
22 10 18 20 2 10

输出 1

1
0
4
50

说明

对于第一组测试数据，下表解释了只有“2 秒”满足限制。