题意描述

定义两个 01 串 $S,T$ 满足 $S\rightarrow T$ 当且仅当 $S$ 中值为 $1$ 的下标集合是 $T$ 中值为 $1$ 的下标集合的子集，定义 $S\leftarrow T$ 当且仅当 $T\rightarrow S$ 。

小诗有一个长为 $n$ 的 01 串序列 $s_1,s_2,\cdots,s_n$ ，其中每个 01 串长度为 $m$ ，她想知道有多少子序列 $1\leqslant p_1<p_2<\cdots<p_k\leqslant n$ ，使得存在 $1\leqslant t\leqslant k$ 满足 $s_{p_1}\rightarrow s_{p_2}\rightarrow\cdots\rightarrow s_{p_t}\leftarrow s_{p_{t+1}}\leftarrow\cdots\leftarrow s_{p_k}$ 。

由于答案过大，你只需告诉她答案 $\bmod 10^9+7$ 的值。

输入格式

第一行两个正整数 $n,m$ 。

第二行 $n$ 个非负整数，第 $i$ 个数表示 $s_i$ 的十进制表示，我们定义一个二进制串 $s_{1,2,\cdots,m}$ 的十进制表示为 $\sum_{i=1}^{m} s_i2^{i-1}$ 。

输出格式

一行一个非负整数，表示答案。

样例

样例输入 #1

4 2
0 3 2 1

样例输出 #1

11

样例解释 #1

子序列 $\{1\},\{2\},\{3\},\{4\},\{1,2\},\{2,3\},\{1,3\},\{2,4\},\{1,4\},\{1,2,3\},\{1,2,4\}$ 均合法。

样例 2~5 见下发文件。

数据范围

对于所有测试点，保证 $1\leqslant n\leqslant 3\times 10^5,1\leqslant m\leqslant 20$ 。

请注意，本题大多数算法常数较小，因此出题人给出的数据范围较大。