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

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

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

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

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