e-olymp
Змагання

July 9 - ADA Training

Декомпозиции графа

Однажды Жомарт решал задачу маршрутизации на сетях. Он обнаружил, что его граф ориентированный и ациклический. Когда Серик пришел посмотреть на задачу, он был удивлен тем, что имеется множество способов декомпозиции графа Жомарта в набор реберно непересекающихся путей. Друзья уже начали думать, сколькими способами это можно сделать. Пожалуйста, помогите им.

Входные данные

Первая строка содержит два целых числа n и m (1n1000, 1m499500). Каждая из следующих m строк содержит два целых числа i, j означающих что в графе имеется ориентированное ребро из вершины i в вершину j.

Выходные данные

Вывести одно число – ответ к задаче по модулю 109 + 7.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 3
1 2
2 3
1 3
Вихідні дані #1
2
Джерело 2014 KBTU Open, Весна Казахстан, Алма-Ата, 20 Апреля, Задача F