Інопланетний підрахунок#3541
Нацукі та її друзі були викрадені у космос інопланетянином і подружилися з багатьма інопланетянами. Під час космічної подорожі вона помітила, що руки інопланетян часто дуже відрізняються від людських. У певного виду інопланетян на руці є пальців і правил згинання. Кожне правило згинання описує, що палець завжди згинається, коли згинається палець . Однак це правило не завжди означає, що палець згинається, коли згинається палець .
Коли вона рахувала числа за допомогою пальців, її зацікавило, скільки чисел її інопланетні друзі можуть порахувати за допомогою пальців. Однак, оскільки деякі друзі мали занадто складні набори правил, вона не могла їх обчислити. Чи могли б ви написати програму для неї?
Перша строка містить два цілі числа та (1 \le N \le 1000; 0 \le M \le 1000) у цьому порядку. Наступні рядків описують правила згинання. Кожен рядок містить два цілі числа S_i та D_i у цьому порядку, що означає, що палець D_i завжди згинається, коли згинається палець S_i. Будь-який палець з'являється не більше одного разу в .
Обчисліть, скільки чисел її інопланетні друзі можуть порахувати за допомогою пальців. Виведіть відповідь за модулем в одному рядку.
Приклад 1