Counting Forwarding Paths in a Social Network

In an experimental small-scale social network, it is observed that sometimes a popular message is eventually forwarded by everyone. To study this phenomenon, we wish to count the number of possible ways a message can be forwarded. The initial sender is numbered \(1\), and the other users are numbered consecutively \(2,3,\dots,n\).

The network’s friend relationships are known; that is, for any two users \(a\) and \(b\), if user \(a\) can see the messages sent by user \(b\), then an edge from \(a\) to \(b\) exists. Note that these relationships may be one‐directional, i.e. \(a\) might be able to see \(b\)’s messages while \(b\) cannot see \(a\)’s.

It is assumed that if a user sees that several of his friends have forwarded the same message, he will choose to forward it from exactly one of them (and he forwards at most once). Different choices are counted as different forwarding processes.

The problem is to count the total number of possible forwarding paths (spanning arborescences with root \(1\)) such that every user eventually forwards the message. Since the answer can be huge, output it modulo \(10^4+7\) (i.e. modulo \(10007\)).

Hint: By reversing the friend relationships, the problem reduces to counting the number of spanning trees (arborescences) rooted at \(1\). This can be solved using the Matrix-Tree Theorem for directed graphs.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of users and the number of friend relationships, respectively.

The next \(m\) lines each contain two integers \(a\) and \(b\), which indicates that user \(a\) can see the messages sent by user \(b\).

outputFormat

Output a single integer: the number of possible forwarding paths modulo \(10^4+7\) (i.e. modulo \(10007\)).

sample

3 3
2 1
3 1
3 2

2