#P18401. Clique Challenge

Clique Challenge

Clique Challenge

图 GG 的一个团是它的一个顶点集合 XX,满足 XX 中任意两个不同的顶点之间都有一条边。

给定一个有 nn 个顶点、mm 条边的无向图 GG,求它的不同非空团的数量。

输入格式

第一行包含两个整数 n,mn,m,分别表示顶点数和边数,1≤n,m≤10001\le n,m\le1000。

接下来 mm 行,每行包含两个整数 ui,viu_i,v_i,描述顶点 ui,viu_i,v_i 之间的一条无向边,1≤ui,vi≤n1\le u_i,v_i\le n,且 ui≠viu_i\ne v_i。

保证任意两个不同顶点之间至多有一条边,即没有重边和自环。

输出格式

输出一行一个整数,表示非空团的数量。答案可能很大,输出它对 109+710^9+7 取模后的结果。

原样例 1

3 2
1 2
2 3
5

原样例 2

3 3
1 2
1 3
2 3
7

原样例说明

第一个样例的团为 {1},{2},{3},{1,2},{2,3}\{1\},\{2\},\{3\},\{1,2\},\{2,3\}。

第二个样例的团为 $\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$。