Рыцари

시간 제한2초메모리 제한1024 MB

요약

키 순서대로 늘어선 n명의 기사에게 m번의 자리 교환을 적용한 뒤, 작은 키의 기사가 더 앞에 있는 쌍의 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 6점
유형: 해시맵, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

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

출력

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

예제1

예제 1
입력
```
5 3
1 3
2 3
2 5
```
예상 출력
```
7
```