Mr. Borris’s Shopping Complex

In a shopping complex dedicated to cake and pencils, there are M shops numbered from 0 to M-1. Each shop is either a cake shop or a pencil shop.

N merchants trade with these shops. Each merchant trades with all (& only) the shops numbered from A_i to B_i (both inclusive).

Each mechant should pay a fee to Mr. Borris, the owner of the shopping complex for trading with the shops in his shopping complex.

For merchant i, the fee F_i is calculated as,
F_i = (number of cake shops he traded with) x (number of pencil shops he traded with)

Mr. Borris knows the shops the merchants are to trade with. (i.e. A_i and B_i values for all i are given).

Mr. Borris now has to decide which of the shops are going to be cake shops and which are going to be pencil shops. Place the shops so that the total revenue from the fees (ΣF_i) is maximized. (i.e. for each x, (0 \(<\) x \(<\) M-1) you need to decide whether x^th shop is a cake shop or a pencil shop so that ΣF_i is maximized.)

Output the maximum revenue Mr. Borris can earn from fees (maximized ΣF_i) modulo 10⁹+7.

Input Format

First line of the input contains 2 integers, M and N.
N lines will follow, with each having 2 integers, Aⁱ and Bⁱ.

Output Format

One integer. (maximized ΣFi) modulo 10⁹+7.

Constraints

• 0 \(<\) M \(<\) 10¹⁶
• 0 \(<\) N \(<\) 50000
• 0 \(\leq\) Aⁱ \(\leq\) Bⁱ \(\leq\) M  

Limits

• Time Limit: 1s
• Memory Limit: 256MB

Sample Input 0

6 2
2 5
0 0

Sample Output 0

4