Migrated from Lutece 2580 不死人的背包

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在黑暗之魂系列中，管理背包的负重是不死人的一门学问，如果背包过重，可能会使不死人的奔跑速度减慢，也会使翻滚的无敌帧变短导致容易被敌人抓到破绽，所以不死人在捡到掉落的物品时可能会选择性地把背包中的东西丢弃来使得负重达到良好的平衡。

现在不死人有 $n$ 件物品，当前不死人的最大负重为 $m$，每件物品互不相同，每件物品都具有它的重量，现在不死人决心要丢弃第 $i\ (1\leq i\leq n)$ 件物品，在剩下的物品中挑选一些物品装入背包使得背包负重恰好为 $j\ (1\leq j\leq m)$。对于每一对 $(i, j)$ 满足 $1\leq i \leq n$ 且 $1\leq j \leq m$ ，不死人想知道有多少种不同的装包方式，于是总共有 $nm$ 个询问，请对每一个询问的答案对于 $10^9+7$ 取模，输出所有答案取模后的异或和。不死人想要努力，可惜防火女看了一眼他的面板发现这位不死人的智力只有个位数，所以只能把这个问题留给你帮忙解决了，你能回答吗？

设一种装包方式中选择放入背包的物品的集合为 $S$，而另一种装包方式中选择的物品集合为 $T$，当 $S\neq T$ 时，我们称这两种装包方式不同。

Input

第一行包括两个正整数 $n$ 和 $m$。

第二行包括 $n$ 个正整数 $w_i$。

Output

答案仅包括一个正整数，为总共 $nm$ 个询问的答案取模后的异或和。

Samples

3 2
1 1 2

3

Constraints

$1\leq n,m\leq 5000$ $1\leq w_i \leq 5000$

Resources

2021 UESTC ICPC Training for Dynamic Programming