题目背景

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$ 求余。

样例 #1

样例输入 #1

2 3
2 4

样例输出 #1

7

样例 #2,3,4,5

点我下载大样例

提示

【样例解释】

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

【数据范围】

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