题目描述
测试完毕之后，研究者们现在要用 Misaka Network 进行任务。当前能处理任务的个体一共有 $N$ 个，以及 $M$ 个处理任务的方案（可能相同），第 $i$ 个方案给出一个 $N$ 位二进制数 $A_i$，表示选用 $A_i$ 这个集合的个体进行任务。现在一共要进行 $K$ 次任务，每次任务可以选取任意一个方案，然后由这个方案的集合 $A_i$ 的所有个体合作完成，要求至少有一个个体参加了所有的 $K$ 次任务。
求出不同的选择方式数对 $10^9+7$ 取模的结果，两种选择方式不同，当且仅当它们在某一次任务选择的方案的编号不同。
输入格式
第一行三个整数 $N$、$M$、$K$。
接下来一行 $M$ 个整数 $A_i$，以十进制的方式给出。
输出格式
一行一个整数，表示方案数对 $10^9+7$ 取模的结果。
样例 1
input
2 3 4
1 2 3output
31
样例 2
input
4 8 8
7 2 8 2 4 3 15 4output
456160
数据范围与提示
对于所有数据 $1 \leq N \leq 22,1 \leq M \leq 10^6,1 \leq K \leq 10^9,0 \leq A_i < 2^N$。
| 子任务编号 | 分值 | $N$ | $M$ | $K$ | 特殊性质 |
|---|---|---|---|---|---|
| 1 | $5$ | $\leq 4$ | $\leq 8$ | $\leq 8$ | - |
| 2 | $10$ | $\leq 7$ | $\leq 1000$ | $\leq 10$ | - |
| 3 | $15$ | $\leq 7$ | $\leq 10^5$ | $\leq 10^9$ | - |
| 4 | $15$ | $\leq 10$ | $\leq 10^5$ | $\leq 10^9$ | - |
| 5 | $15$ | $\leq 15$ | $\leq 10^5$ | $\leq 10^9$ | - |
| 6 | $20$ | $\leq 20$ | $\leq 10^5$ | $\leq 10^9$ | $A_i$ 在 $[0,2^N)$ 中等概率随机 |
| 7 | $20$ | $\leq 22$ | $\leq 10^6$ | $\leq 10^9$ | - |