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\lt t_i≤n）$，描述第$i$个速度技能。

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