29321번 - Рыцари 다국어

문제

Ария Старк --- девочка, которой чужды платья, резиночки и куклы, но не чуждо воинское искусство. Она постоянно занимается со своим учителем боем на мечах и хочет в скором времени быть способной постоять за себя и своих любимых.

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

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

입력

Первая строка входного файла содержит два числа $n$ и $m$ $(1 \le n \le 10^{18}, 1 \le m \le 10^{5})$ --- количество рыцарей и количество приказов Арии поменяться местами. Следующие $m$ строк содержат эти приказы, по одному в каждой строке. Приказ состоит из двух различных чисел, разделенных пробелом --- позиции двух рыцарей, которые меняются местами. Изначально на первом месте стоит самый высокий рыцарь, а количество пар таких, что меньший рыцарь стоит ближе к началу равно нулю. Рост всех рыцарей различен.

출력

Выведите одно число --- ответ на задачу по модулю 10ドル^9 + 7$

제한

힌트