强攻计策

Problem Description

Alice正在练习跑步。 Alice的每次练习将持续$n$秒的时间，在一开始，Alice在练习中以一个恒定的速度跑步。 但Alice觉得这样太慢了，她想要在跑步时间不变的情况下，跑得尽可能的远，所以她决定学习一些速度技能。 每个速度技能可以用$s,t$描述，表示学习了这个速度技能后，Alice在$[s,t]$区间内的目标速度增加$1m/s$ Alice在跑步的过程中，如果她的当前速度低于目标速度，她将会以$1m/s^2$的加速度加速，如果她的当前速度高于目标速度，她将会以$-1m/s^2$的加速度减速，如果她的当前速度等于目标速度，则保持这个速度。 Alice想要知道，她在学习了前$i$个速度技能之后，她相比于没学习任何技能时能多跑多远。 答案对$10^9+7$取模。

Input

第一行包含一个整数T（$1 \leq T \leq 5$），表示数据组数 接下来每一组数据的第一行包含两个整数$n,m$（$1 \leq n,m \leq 100000$），表示Alice跑步的时间和学习的速度技能数量。 接下来$m$行，每行包含两个整数$s_i,t_i$（$0 \leq s_i < t_i \leq n$），描述第$i$个速度技能。

Output

每组数据$m$行，每行包含一个整数，表示Alice相比于没学习任何技能时能多跑多少米

Sample Input

1
5 2
0 4
1 3

Sample Output

4
6

Source

2024“钉耙编程”中国大学生算法设计超级联赛（2）