Alien's Counting#3541
Natsuki and her friends were taken to space by an alien and made friends with many 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 fingers and bend rules on a hand. Each bend rule describes that a finger always bends when a finger bends. However, this rule does not always imply that the finger bends when the finger bends.
When she was counting numbers with the fingers, she was anxious about 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?
The first line contains two integers and (1 \le N \le 1000; 0 \le M \le 1000) in this order. The following lines describe the bend rules. Each line contains two integers S_i and D_i in this order, which mean that the finger D_i always bends when the finger S_i bends. Any finger appears at most once in .
Calculate how many numbers her alien friends can count with the fingers. Print the answer modulo on a line.
Example 1