Alien`s Counting
Натсуки и её друзья были похищены в космос инопланетянином, где они завели множество новых друзей среди инопланетян. Во время путешествия она заметила, что руки инопланетян часто сильно отличаются от человеческих. У одного из видов инопланетян на руке N пальцев и M правил сгибания. Каждое правило сгибания указывает, что палец A всегда сгибается, если сгибается палец B. Однако это не означает, что палец B сгибается, если сгибается палец A.
Когда она считала числа с помощью пальцев, её заинтересовало, сколько чисел могут посчитать её инопланетные друзья с помощью своих пальцев. Однако из-за сложных наборов правил у некоторых друзей она не смогла это выяснить. Можете ли вы написать программу, которая поможет ей?
Входные данные
N M S 1 D_1 S 2 D_2 ... S M D_M
Первая строка содержит два целых числа N и M (1 ≤ N ≤ 1000; 0 ≤ M ≤ 1000) в указанном порядке. Следующие M строк описывают правила сгибания. Каждая строка содержит два целых числа S_i и D_i, что означает, что палец D_i всегда сгибается, когда сгибается палец S_i. Любой палец появляется не более одного раза в S.
Выходные данные
Определите, сколько чисел могут посчитать её инопланетные друзья с помощью пальцев. Выведите ответ по модулю 1000000007 в отдельной строке.