HaHa's Morning
HaHa сегодня очень рад, ведь он собирается участвовать в 7-м Программном Конкурсе Университета Хунань. Проснувшись утром, он захотел как можно быстрее добраться до университета, но вспомнил, что у него есть еще N дел, которые нужно выполнить перед поездкой.
Сначала HaHa подумал, что существует N! (факториал от N) способов выполнить все дела. Однако вскоре он понял, что это невозможно из-за некоторых раздражающих ограничений: определенные дела должны быть выполнены раньше других. Теперь HaHa интересуется, сколько существует способов выполнить все дела, и просит вас помочь ему в этом. Ваша задача — определить количество возможных способов завершить его дела.
Входные данные
Входные данные содержат несколько тестовых случаев. Первая строка каждого случая содержит два натуральных числа: N (количество дел) и M ≤ 400 (общее количество ограничений).
Следующие M строк описывают ограничения. Каждая строка содержит два положительных целых числа A и B, где дело A должно быть выполнено перед делом B.
Ввод заканчивается концом файла. Гарантируется, что 1 ≤ A, B ≤ N ≤ 17.
Выходные данные
Для каждого тестового случая выведите одно число: количество способов завершить все дела.