Submerged Platforms Damage Calculation

You are given a water surface with n platforms (numbered from 1 to n) which are initially unsunken. There are m pairs of distinct platforms that are connected by bidirectional links. Lottia fights her enemy for k rounds. In each round, she can choose an arbitrary subset (possibly empty) of the currently unsunken platforms to sink, with the only restriction that she cannot sink all the current platforms. After that, she selects as many platforms as possible from the remaining (unsunken) platforms such that every two chosen platforms are connected (i.e. they form a clique in the induced graph). On each of the chosen platforms, she summons a distinct water phantom and the number of phantoms (i.e. the size of the clique) equals the damage dealt by that round.

Her overall damage is the sum of the numbers of phantoms summoned in each round. Two sinking strategies are considered different if, in at least one round, the set of platforms sunk is different (the way of choosing the clique does not affect the strategy).

Your task is to calculate the sum of the damages over all possible sinking strategies over the k rounds, and output the answer modulo \(10^9+7\).

Note: The maximum clique size in the graph induced by a set \(V\) is defined as the largest \(r\) such that there exists a subset \(X \subseteq V\) with \(r\) vertices forming a clique. In each round, if the set of remaining platforms is \(V\), Lottia's round damage is \(\omega(V)\), the maximum clique size of the induced subgraph on \(V\).

Simplified: You are given an undirected graph (with no self‐loops and no multiple edges). In each of the k rounds you choose an arbitrary nonempty subset (which may be the entire set) of the current vertices (representing the platforms to remain) by sinking the others. For each round, the damage equals the maximum clique size in the remaining graph. Compute the sum over all rounds and over all sinking strategies modulo \(10^9+7\).

inputFormat

The first line contains three integers n m k \(\,(1 \leq n \leq N,\ 0 \leq m \leq M,\ 1 \leq k \leq K)\,

Then m lines follow, each containing two integers u v (1-indexed) representing an edge between platform u and platform v.

Note: The graph does not contain self-loops or multiple edges.

outputFormat

Output a single integer — the sum of damages over all sinking strategies (across all k rounds), modulo \(10^9+7\).

sample

1 0 1

1