测试数据来自 Zmmsss/3065

题目描述

输入格式

第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中相同。
接下来 t 行每行两个整数 n, m，表示一组询问。

输出格式

输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答案除以 10^9 + 7 的余数。

样例输入1

1 2
3 3

样例输出1

1

样例输入2

2 5
4 5
6 7

样例输出2

0
7

样例说明

评测用例规模与约定

对于所有评测用例，1 ≤ k ≤ 10^8, 1 ≤ t ≤ 10^5, 1 ≤ n, m ≤ 10^18，且 k 是质数。
评测时将使用 10 个评测用例测试你的程序，每个评测用例的限制如下：
评测用例编号……t………………………n，m……………………k
1,2…………………≤1……………………≤2000……………………≤100
3,4………………≤10^5………………≤2000……………………≤100
5,6,7………………≤100…………………≤2000…………………≤100
8,9,10……………≤10^5………………≤2000…………………≤10^8