#570. 「LibreOJ Round #11」Misaka Network 与任务

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

测试完毕之后,研究者们现在要用 Misaka Network 进行任务。当前能处理任务的个体一共有 NNN 个,以及 MMM 个处理任务的方案(可能相同),第 iii 个方案给出一个 NNN 位二进制数 AiA_iAi,表示选用 AiA_iAi 这个集合的个体进行任务。现在一共要进行 KKK 次任务,每次任务可以选取任意一个方案,然后由这个方案的集合 AiA_iAi 的所有个体合作完成,要求至少有一个个体参加了所有的 KKK 次任务。

求出不同的选择方式数对 109+710^9+7109+7 取模的结果,两种选择方式不同,当且仅当它们在某一次任务选择的方案的编号不同。

输入格式

第一行三个整数 NNNMMMKKK

接下来一行 MMM 个整数 AiA_iAi,以十进制的方式给出。

输出格式

一行一个整数,表示方案数对 109+710^9+7109+7 取模的结果。

样例

样例输入 1

2 3 4
1 2 3

样例输出 1

31

样例输入 2

4 8 8
7 2 8 2 4 3 15 4

样例输出 2

456160

数据范围与提示

对于所有数据 1≤N≤22,1≤M≤106,1≤K≤109,0≤Ai<2N1 \leq N \leq 22,1 \leq M \leq 10^6,1 \leq K \leq 10^9,0 \leq A_i < 2^N1N22,1M106,1K109,0Ai<2N

子任务编号 分值 NNN MMM KKK 特殊性质
1 555 ≤4\leq 44 ≤8\leq 88 ≤8\leq 88 -
2 101010 ≤7\leq 77 ≤1000\leq 10001000 ≤10\leq 1010 -
3 151515 ≤7\leq 77 ≤105\leq 10^5105 ≤109\leq 10^9109 -
4 151515 ≤10\leq 1010 ≤105\leq 10^5105 ≤109\leq 10^9109 -
5 151515 ≤15\leq 1515 ≤105\leq 10^5105 ≤109\leq 10^9109 -
6 202020 ≤20\leq 2020 ≤105\leq 10^5105 ≤109\leq 10^9109 AiA_iAi[0,2N)[0,2^N)[0,2N) 中等概率随机
7 202020 ≤22\leq 2222 ≤106\leq 10^6106 ≤109\leq 10^9109 -