zzh 与宝可梦运动会

题目描述

一年一度的宝可梦运动会就要开始啦！zzh 和他的宝可梦们要参加运动会的开幕式，他打算把 $n$ 只宝可梦排成一排表演节目。

我们知道，宝可梦共有 $m$ 种单属性，我们将它们编号为 $1,2,\cdots,m$ 。除此之外，还有很多由这 $m$ 种单属性组合成的双属性，它的形式是满足 $1\le a < b \le m$ 的有序对 $(a,b)$。宝可梦世界中存在的双属性满足如下的条件：有 $k$ 个区间 $[l_{i}, r_{i}]$ $(i = 1,2,\cdots,k)$ ，它们对应的双属性集合分别为 $\{(x,y)|l_{i}\le x < y \le r_{i}\}$，而宝可梦世界中存在的双属性就是这 $k$ 个集合的并。我们设所有不同的单/双属性共有 $t$ 种。

现在 zzh 准备在每个位置等概率地随机安排一种属性的宝可梦（即每种单/双属性各 $\frac{1}{t}$ 的概率），这样总共有 $t^{n}$ 种不同的方案。接下来，zzh 要给宝可梦们分组，他规定每组是 $[1,n]$ 的一个子区间，且每只宝可梦必须属于且只属于一个组。同时他认为，如果一组内相邻的宝可梦属性相近，就能够取得最佳的表演效果，这里属性相近指的是两只宝可梦至少具有一种共同的属性。于是 zzh 会将宝可梦们分为尽可能少的连续几组，其中同组的宝可梦满足组内任意两个相邻的宝可梦属性相近（显然这样的分组方法是唯一的）。

zzh 希望了解他和宝可梦们的表演大概能取得多好的效果，因此他想知道所有不同方案中宝可梦们分成的组数的数学期望是多少。但是我们知道 zzh 的概率论实在是太菜了，所以他把这个问题丢给了你，希望你能帮助他算出答案。为了避免浮点运算，你只需要告诉他答案乘上 $t^{n}$ （显然这是个整数）对 $(10^{9}+7)$ （一个质数） 取模的值即可。

输入

第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。

接下来依次给出每组测试数据。对于每组测试数据：

第一行包含三个整数 $n$，$m$ 和 $k$，含义见题目描述。

接下来 $k$ 行，第 $i$ 行包含两个整数 $l_{i}$ 和 $r_{i}$，表示题目描述中的第 $i$ 个区间的左右端点。

保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。

保证所有的数据满足 $1 \leq T \leq 20$，$1 \le n, m \le 10^{18}$，$1 \le k \le 100000$，保证 $k > 10000$ 的数据不超过 $20\%$。

保证所有的数据满足 $1 \le l_{i} \le r_{i} \le m$。

输出

对于每组数据，输出一行，包含一个整数，表示题目所求的答案。

输入样例

2
2 2 2
1 2
1 2
1000000000000000000 1000000000000000000 2
1 2
2 4

输出样例

11
510010785

样例解释

对于第一组数据，双属性只有 $(1,2)$ 这一种。因此总共有 $9$ 种方案，其中 $[1,2]$ 和 $[2,1]$ 两种情况分成的组数为 $2$，$[1,1],[1,(1,2)],[2,2],[2,(1,2)],[(1,2),1],[(1,2),2],[(1,2),(1,2)]$ 等七种情况分成的组数为 $1$ 。故答案为 $\displaystyle\frac{1\times7+2\times2}{9}\times9=11$。