# Problem A

All Colourings

Given an undirected graph $G =
(V,E)$, a *proper* colouring of $G$ with $K$ colours is an assignment of values
from $1$ through
$K$ to each vertex so that
each edge receives a different value/colour. That is, a proper
$K$-colouring is a mapping
$\sigma : V \rightarrow \{ 1, 2,
\ldots , K\} $ such that $\sigma (u) \neq \sigma (v)$ for each
edge $(u,v)$ of
$E$.

So much effort has been spent finding proper colourings of
graphs that the *improper* colourings are left out.
Thatâ€™s a shame, because all colourings are beautiful!

You want to examine every possible colouring to see how many edges receive the same colour at its endpoints. That is, for each value $b$ from $0$ to $|E|$ you should compute the number of $K$-colourings $\sigma : V \rightarrow \{ 1, 2, \ldots , K\} $ such that the number of edges $(u,v)$ of $G$ receiving the same colour on both endpoints (i.e. $\sigma (u) = \sigma (v)$) is exactly equal to $b$. Since this number can be large for the given input bounds, you should instead report what this value would be if it was reduced modulo $1\, 000\, 000\, 009$. Note we are calling any mapping $\sigma : V \rightarrow \{ 1, 2, \ldots , K\} $ a $K$-colouring whether it is proper or not.

The first sample input is illustrated below. All colourings of the graph with $K = 2$ colours are shown and are arranged according to the number of edges whose endpoints receive the same colour.

## Input

The first line of input contains three integers $N$ ($1 \leq N \leq 20$), $M$ ($0 \leq M \leq 20$), and $K$ $(1 \leq K \leq 10^9)$. Here, $N$ is the number of nodes in the graph, $M$ is the number of edges in the graph, and $K$ is the number of colours we will use in our $K$-colouring.

Then $M$ lines follow, each containing a pair of integers $u,v$ $(1 \leq u,v \leq N, u \neq v)$ indicating $u$ and $v$ are connected by an undirected edge. No edge will appear more than once in the input.

## Output

Output a single line with $|E|+1$ values $c_0, c_1, \ldots , c_{|V|}$ in that order with a single space separating consecutive values. Here, $c_ b$ is the number of $K$-colourings of $G$ that have exactly $b$ monochromatic edges, reduced modulo $1\, 000\, 000\, 009$.

Sample Input 1 | Sample Output 1 |
---|---|

3 2 2 1 2 1 3 |
2 4 2 |

Sample Input 2 | Sample Output 2 |
---|---|

4 4 2 1 2 2 3 3 4 4 1 |
2 0 12 0 2 |

Sample Input 3 | Sample Output 3 |
---|---|

4 4 3 1 2 2 3 3 1 1 4 |
12 42 18 6 3 |