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