Description

On the water surface where Rhodeia is located, there are $n$ platforms, and initially none of them are submerged. There are $m$ pairs of different platforms connected to each other. Rhodeia fights the enemy for $k$ rounds. In each round, she may choose some platforms that are not yet submerged and make them sink (she may choose none, but she cannot make all platforms sink). Then she will choose as many platforms as possible such that every two chosen platforms are connected, and summon a different “Hydro Mimic” on each chosen platform. After $k$ rounds, the damage Rhodeia deals to the enemy is the sum, over all rounds, of the number of “Hydro Mimics” summoned in that round. Rhodeia wants to know: over all her different choices of sinking platforms, what is the total sum of damage?

Two plans are considered different if and only if there exists a round in which the sets of platforms sunk in that round are different; the platforms used to summon “Hydro Mimics” do not matter. Since the answer may be very large, output it modulo $10^9+7$.

Brief statement: Given an undirected graph with no self-loops and no multiple edges, for $k$ rounds, in each round you may delete any proper subset of the current vertex set. For all plans, compute the sum of the maximum clique size of the remaining graph after each round, modulo $10^9+7$.

Input Format

The first line contains three integers $n,m,k$, representing the number of platforms, the number of connected platform pairs, and the number of rounds.

The next $m$ lines each contain two integers $x,y$, indicating that platform $x$ and platform $y$ are connected. Platforms are numbered from $0$ to $n-1$. It is guaranteed that there are no self-loops and no multiple edges.

Output Format

Output one line with one integer, representing the answer.

2 1 2
0 1

14

5 7 100
0 1
1 2
2 3
3 4
0 4
0 3
0 2

969766107

Hint

Sample Explanation

There are five different plans:

• In round 1, sink platform $0$; in round 2, choose none. The damage is $1+1=2$.
• In round 1, sink platform $1$; in round 2, choose none. The damage is $1+1=2$.
• In round 1, choose none; in round 2, sink platform $0$. The damage is $2+1=3$.
• In round 1, choose none; in round 2, sink platform $1$. The damage is $2+1=3$.
• Choose none in both rounds. The damage is $2+2=4$.

The total damage over the five plans is $2+2+3+3+4=14$.

Constraints

This problem uses bundled testdata, and the constraints follow the table below:

For all testdata: $2\le n\le 28$, $1\le m\le\frac{n(n-1)}{2}$, $1\le k\le 10^9$.

Hint

Please pay attention to the time and memory limits.

Note

Minecraft OI Round 4 A.
idea & solution: Kagamine Rin. check: namespace_std.

Translated by ChatGPT 5