#E. Yet Another Yummy Problem

传统题

3000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

yummy 为什么是云斗滴神？That's a good question！

某天，yummy 给了你 $n$ 个正整数 $x_1,x_2,\ldots,x_n$ ，第 $i$ 个正整数满足约束 $0\le x_i\le r_i$ 。现在，祂希望你能解决如下问题：

求有多少组本质不同的 $\{x_n\}$ 满足 $x_1\oplus x_2\oplus\ldots \oplus x_n$ 是 $m$ 的倍数，其中 $\oplus$ 表示按位异或。

对于两组 $\{x_n\}, \{x_n'\}$ ，两者本质不同当且仅当 $\exist k\in[1,n]$ 满足 $x_k \neq x_k'$ 。

输入的第一行有两个正整数 $n,m$ ，表示正整数个数和异或值的要求。

第二行有 $n$ 个正整数 $r_1,r_2,\ldots,r_n$ ，表示每个正整数的上限。

输出一行一个自然数，表示符合题意的方案数。由于方案数可能过大，你需要将答案对 $10^9+7$ 求余。

2 3
2 4

【样例解释】

下列表格中 T 表示 $x_1\oplus x_2$ 是 $3$ 的倍数，F 表示不是。

$x_1\backslash x_2$	$0$	$1$	$3$	$4$
$0$	T	F	T	F
$1$	F	T	F	F
$2$	F	T	F	T

【数据范围】

测试点编号 $T$	$n\le$	$r_i\le$	特殊性质
$1$		$10^9$
$2$	$2$	$10^4$
$3\sim 5$	$2$	$10^9$
$6\sim 14$	$T$
$15\sim 16$	$15$		$m=16$
$17$		$=2^{29}-1$
$18\sim 20$		$10^9$

对于全体数据，保证 $1\le n\le 15$ ， $1\le r_i\le 10^9$ ， $1\le m\le 20$ 。