eolymp
bolt
Try our new interface for solving problems
Məsələlər

Alien`s Counting

Alien`s Counting

Zaman məhdudiyyəti 8 saniyə
Yaddaşı istafadə məhdudiyyəti 32 MiB

Natsuki and her friends were taken to the space by an alien and made friends with a lot of aliens. During the space travel, she discovered that aliens’ hands were often very different from humans’. Generally speaking, in a kind of aliens, there are N fingers and M bend rules on a hand. Each bend rule describes that a finger A always bends when a finger B bends. However, this rule does not always imply that the finger B bends when the finger A bends.

When she were counting numbers with the fingers, she was anxious how many numbers her alien friends can count with the fingers. However, because some friends had too complicated rule sets, she could not calculate those. Would you write a program for her?

Giriş verilənləri

N M S 1 D_1 S 2 D_2 ... S M D_M

The first line contains two integers N and M (1N1000; 0M1000) in this order. The following M lines mean bend rules. Each line contains two integers S_i and Di in this order, which mean that the finger Di always bends when the finger S_i bends. Any finger appears at most once in S.

Çıxış verilənləri

Calculate how many numbers her alien friends can count with the fingers. Print the answer modulo 1000000007 in a line.

Nümunə

Giriş verilənləri #1
5 4
2 3
3 4
4 3
5 4
Çıxış verilənləri #1
10
Mənbə ACM-ICPC Japan Alumni Group Summer Camp 2010, Day 4, Tokyo, Japan, 2010-09-20