这题的出题思路……来源于CTSC的NOIP十合一以及matthew99大爷的UOIP十合一……

这题是本人出给校内娱乐赛的一道题（并且被AC了），感觉蛮有意思的就放到了blog上。

另外为什么checker这么慢？因为要防止随便乱试啊2333

下面是正题。

子集计数问题

题目描述

给定无向图 $G=(V,E)$，$|V|=n$，$|E|=m$，$V$ 中的点编号为 $1,2,...,n$。求有多少个子集 $V'\subseteq V$ 满足 $|V'|=k$ 且 $\forall (u,v)\in E,u\not\in V'\lor v\not\in V'$。由于答案可能很大，只需输出答案对 $p$ 取模的结果。

输入格式

本题为提交答案题。所有输入数据 subset1.in ~ subset10.in 见输入数据下载。

输入第 $1$ 行包含 $4$ 个用空格分隔的正整数 $n$，$m$，$k$，$p$，分别表示 $|V|$，$|E|$，要求的 $|V'|$ 的大小以及模数。

随后 $m$ 行，每行包含 $2$ 个用空格分隔的正整数 $a_i$，$b_i$，描述 $G$ 中的边 $(a_i,b_i)\in E$。

输出格式

针对给定的 $10$ 个输入文件 subset1.in ~ subset10.in，你需要分别提交你的输出文件 subset1.out ~ subset10.out。

输出文件共 $1$ 行，包含 $1$ 个整数，表示子集 $V'$ 的个数对 $p$ 取模的值。

样例一

input

6 9 2 10000
1 2
1 3
1 4
4 3
2 5
5 6
3 5
3 6
6 4

output

6

explanation

共有 $6$ 个这样的子集 $V'$，分别是：$\{1,5\}$，$\{1,6\}$，$\{2,3\}$，$\{2,4\}$，$\{2,6\}$，$\{4,5\}$。

样例二

input

17 16 5 10000
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 10
7 11
8 12
8 13
10 14
10 15
12 16
15 17

output

1528

评分方式

本题共有 $10$ 个测试点，每个测试点都有一定分值。对于每个测试点，如果选手的输出与标准答案一致，则得到该测试点的分值，否则不得分。每个测试点的分值由下表给出：

如何测试你的输出

在终端中先切换到该试题的目录下：（windows用户请使用cmd）

cd subset

我们提供 checker 这个工具来测试你的输出文件是否正确。使用这个工具的方法是，在终端中运行

./checker <case_no>

其中 case_no 是测试数据的编号。例如

./checker 3

将测试 subset3.out 是否正确。（windows用户请使用 checker 3）

在你调用这个程序后，checker 将根据你给出的输出文件给出测试的结果。

下载

输入数据及checker下载