Let's consider undirected graph with \textbf{N} vertices and \textbf{M} edges. How many different ways are there to paint it, if there are only \textbf{K} colours? You need not use all colours in one painting. Two paintings are considered the same if there is such a renumbering of vertices of one painting that leaves the list of edges unchanged, and the colour of its \textbf{i}^th vertex is the same as the colour of \textbf{i}^th vertex of other painting for each \textbf{i}. For example, paintings on picture are the same (renumbering: \textbf{1} → \textbf{1}, \textbf{2} → \textbf{2}, \textbf{3} →4, \textbf{4} → \textbf{3}). \includegraphics{https://static.e-olymp.com/content/81/81333733899b2ae326ca8fc2b491aef19f382311.jpg} \InputFile First line of input file contains three integer numbers: \textbf{N}, \textbf{M} and \textbf{K} (\textbf{1} ≤ \textbf{N} ≤ \textbf{9}, \textbf{1} ≤ \textbf{M} ≤ \textbf{100}, \textbf{1} ≤ \textbf{K} ≤ \textbf{10}). Next \textbf{M} lines contain two integers each - graph edges. Graph may contain parallel edges and loops. Numbers in lines are separated by spaces. \OutputFile Output file must contain one integer number \textbf{R} - answer for the task. \includegraphics{https://static.e-olymp.com/content/a9/a92289eb7a52e5314895454de53e9dadcdb7fe34.jpg}