eolymp
Соревнования

KBTU OPEN 2014 Spring

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

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

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

Первая строка содержит два целых числа 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