Рассмотрим неориентированный граф из \textbf{N} вершин и \textbf{M} ребер. Сколькими способами можно раскрасить его вершины, если всего имеется \textbf{K} различных цветов? В одной раскраске не обязательно использовать все цвета. Две раскраски считаются одинаковыми, если существует такая перенумерация вершин графа, при которой список ребер остается тем же, и цвета соответствующих вершин совпадут. К примеру, две раскраски на рисунке одинаковы (соответствующая перенумерация: \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 Первая строка входного файла содержит три целых числа: \textbf{N}, \textbf{M} и \textbf{K} (\textbf{1} ≤ \textbf{N} ≤ \textbf{9}, \textbf{1} ≤ \textbf{M} ≤ \textbf{100}, \textbf{1} ≤ \textbf{K} ≤ \textbf{10}). Следующие \textbf{M} строк содержат по два целых числа в пределах от \textbf{1} до \textbf{N} --- ребра графа. Граф может содержать кратные ребра и петли. Числа в строках разделены пробелом. \OutputFile Выходной файл должен содержать одно целое число \textbf{R} --- количество различных раскрасок. \includegraphics{https://static.e-olymp.com/content/a9/a92289eb7a52e5314895454de53e9dadcdb7fe34.jpg}