题目描述

Alice正在练习跑步。

Alice的每次练习将持续 $n$ 秒的时间，在一开始，Alice在练习中以一个恒定的速度跑步。

但Alice觉得这样太慢了，她想要在跑步时间不变的情况下，跑得尽可能的远，所以她决定学习一些速度技能。

每个速度技能可以用 $s,t$ 描述，表示学习了这个速度技能后，Alice在 $[s,t]$ 区间内的目标速度增加 $1m/s$

Alice在跑步的过程中，如果她的当前速度低于目标速度，她将会以 $1m/s^2$的加速度加速，如果她的当前速度高于目标速度，她将会以 $−1m/s^2$的加速度减速，如果她的当前速度等于目标速度，则保持这个速度。

Alice想要知道，她在学习了前 $i$ 个速度技能之后，她相比于没学习任何技能时能多跑多远。答案对 $10^9+7$取模。

输入格式

第一行包含一个整数 $T$（$1≤T≤5$），表示数据组数

接下来每一组数据的第一行包含两个整数 $n,m$（$1≤n,m≤100000$），表示Alice跑步的时间和学习的速度技能数量。

接下来 $m$ 行，每行包含两个整数 $s_i,t_i$（$0≤s_i<t_i≤n$），描述第 $i$ 个速度技能。

输出格式

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

输入样例

1
5 2
0 4
1 3

输出样例

4
6