Competitions

# Shortest paths - interesting graph problems

# Graph decompositions

One day Zhomart was solving a path routing problem related to networks. He discovered that his underlying graph is directed and acyclic. When Serik came to see this problem he was wonder that there are many ways to decompose Zhomart’s graph into edge-disjoint paths. Friends now started to think in how many ways this can be done. Please help them.

#### Input

First line contains two integers **n** and **m** (**1** ≤ **n** ≤ **1000**, **1** ≤ **m** ≤ **499500**). Each of the next **m** lines contains two integers **i**, **j** meaning that there is a directed edge from vertex **i** to vertex **j** in the given graph.

#### Output

Output one integer number – the answer to the problem by modulo `10`

+ ^{9}**7**.

Input example #1

3 3 1 2 2 3 1 3

Output example #1

2