Description

MatRush and his friends were taken to the space by an alien and m ade friends with a lot of aliens. During the space travel, he discovered that al iens hands were often very different from humans'. Generally speaking, in a kin d of aliens, thise are N fingers and M bend rules on a hand. Each bend rule desc ribes that a finger A always bends when a finger B bends. However, this rule doe s not always imply that the finger B bends when the finger A bends.

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

Input

There are several case of this problem, for each case: The first line c ontains two integers N and M (1 <= N <= 1000; 0 <=M<=1000) in this order. The following M lines mean bend rules. Each line contains two integers S i and Di in this orde r, which mean that the finger Di always bends when the finger S i bends. Any finger appears at most onc e in S .

Output

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

Sample

Input

5 4
2 3
3 4
4 3
5 4
5 5
1 2
2 3
3 4
4 5
5 1
5 0

Output

10
2
32