시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB111100.000%

문제

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

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

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

입력

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

출력

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

예제 입력 1

5 3
1 3
2 3
2 5

예제 출력 1

7