Розглянемо неорієнтовний граф з \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}