In today's society, seeing messages from friends on social networks has become a part of many people's lives. Usually, after a user posts a message on a social network (such as a Weibo, status, or Tweet), their friends can see this message and may repost it. The message can then continue to be reposted, spreading throughout the entire social network.

In an experimental small-scale social network, we have observed that sometimes a popular message is eventually reposted by everyone. To study the process of this phenomenon, we hope to calculate the number of all possible reposting paths for a message. For programming convenience, we assign the initial message sender the ID 1, and other users are numbered sequentially.

The friendship relationships on the social network are known, meaning that for any two users A and B, we know whether user A can see messages posted by user B. Note that friendship in the social network is directed; that is, A can see B's messages, but B may not be able to see A's messages.

There is another assumption: if a user sees a message posted by multiple friends, they will only choose to repost it from one of them, and they will repost it at most once. Reposts from different friends are considered different situations.

If arrows are used to represent friendship relationships, the figure below shows all possible reposting scenarios for a message in a certain social network. (The initial message is sent by user 1, and the bold arrows indicate a single reposting event.)

Input

The first line of the input contains a positive integer $n$, representing the number of users in the social network; the second line contains a positive integer $m$, representing the number of friendship relationships in the social network.

Following this are $m$ lines, each containing two space-separated integers $a_i$ and $b_i$, indicating a friendship relationship where user $a_i$ can see messages posted by user $b_i$.

Output

Output a single line containing the number of all possible reposting paths for a message, modulo 10007.

Examples

Input 1

4
7
2 1
3 1
1 3
2 3
3 2
4 3
4 2

Output 1

6

Constraints

• For 30% of the data, $1 \le n \le 10$.
• For 100% of the data, $1 \le n \le 250$, $1 \le a_i, b_i \le n$, $1 \le m \le n(n-1)$.