HaHa is so happy today, he is going to participate the \textbf{7}^th Hunan University Programming Contest. He woke up in the morning, and wanted to reach Hunan University as soon as possible, but he realized that he still has \textbf{N} things to do before going on his journey. At first, HaHa thought there must have \textbf{N!} (the factorial of \textbf{N}) ways to get everything done, however, he soon found that this was impossible at all, for the work has some annoying restrictions: some things must be done before getting some other things done. Now HaHa is interested in the number of ways to get everything done, and he asks you for help, so your task is to find how many ways are there to finish his work. \InputFile There are several test cases, each case contains several lines, the first line of each case is two natural numbers \textbf{N}(that described above) and \textbf{M} ≤ \textbf{400} (for the total restrictions for the work). The next \textbf{M} lines describes the restrictions, for each line, there is two positive integers \textbf{A}, \textbf{B}, for the \textbf{A}-th thing must be done before the \textbf{B}-th thing. The input will finish with the end of file, input is guaranteed that \textbf{1} ≤ \textbf{A}\textit{, }\textbf{B}\textit{ ≤ }\textbf{N}\textit{ ≤ }\textbf{17}. \OutputFile For each the case, output one number: the ways to finish the work.