U561829 孤独的Oier

### 题目描述 小X是一个孤独的 Oler，退役后他发现他无法和其他人找到共同的话题。好在小X有 $M$ 名同学，小X希望通过 $K$ 天的交流拉近与他们的关系。这 $M$ 名同学可能感兴趣的话题共有 $N$ 种，我们用一个 $N$ 位的二进制数 $A_i$ 来表示一位同学对于各个话题是否感兴趣。例如，当 $N=3$，$A_i=110_{(2)}$（即十进制数 $6$），表示第 $i$ 位同学对第 $1$、第 $2$ 个话题感兴趣，而对第 $3$ 个话题不感兴趣。 每天，小X会选择一位同学，与其交流一个他感兴趣的话题。由于 Oler 的记忆只有 $7$ 秒，所以小X每天与同学交流的话题必须相同。现在，小X想要知道有多少种不同的方式选择每天交流的同学，使得他能够找到至少一个话题，顺利地完成和他们的交流。两种选取方案不同，当且仅当在某一天小X选择的同学不同。 由于答案可能很大，输出其对 $10^9+7$ 取模的结果。 ### 输入格式 第一行包含三个整数 $N, M, K$，分别表示话题的数量、同学的人数和交流的天数。 第二行包含 $M$ 个整数，其中第 $i$ 个整数表示第 $i$ 位同学感兴趣的话题对应的二进制数的十进制形式。 ### 输出格式 输出一个整数，表示不同的方式数目对 $10^9+7$ 取模后的结果。 #### 输入样例 ``` 3 3 2 6 3 5 ``` #### 输出样例 ``` 9 ``` 样例解释： ①可选择第1个话题进行两天的交流： 方案一：同学一（6）、同学一（6） （代表两天选择交流的同学，下同） 方案二：同学一（6）、同学五（5） 方案三：同学五（5）、同学一（6） 方案四：同学五（5）、同学五（5） ②选择第2个话题交流： 方案一：同学一、同学一（上面已出现，该方案重复，删去） 方案二：同学一、同学三 方案三：同学三、同学一 方案四：同学三、同学三 ③选择第3个话题交流： 方案一：同学三、同学五 方案二：同学三、同学三（上面已出现，该方案重复，删去） 方案三：同学五、同学三 方案四：同学五、同学五（上面已出现，该方案重复，删去） 答案为9 ### 数据范围 - 对于 10% 的数据（测试点1），保证 $N = 1$，$1 \leq M \leq 10^3$，$1 \leq K \leq 10^3$ - 对于 10% 的数据（测试点2），保证所有同学的 $A_i = 0$（无合法方案） - 对于 10% 的数据（测试点3-4），保证 $N \leq 3$，$M \leq 10^3$，$K \leq 10^3$，且存在固定话题组合 - 对于 15% 的数据（测试点5-6），保证 $N \leq 20$，$M \leq 20$，$K \leq 10^3$，适合暴力容斥解法 - 对于 20% 的数据（测试点7），保证 $N \leq 5$，$M \leq 10^3$，$K \leq 10^5$，所有同学有相同的话题组合 - 对于 35% 的数据（测试点8-10），保证 $1 \leq N \leq 20$，$1 \leq M \leq 10^5$，$1 \leq K \leq 10^9$（所有数据的最终约束） 注：固定话题组合指所有同学的 $A_i$ 二进制表示中 1 的位模式相同（如所有同学都支持话题1和2）

无

无

无