Description

肖肖是一个热爱思考的孩子，在他学完了$GCD$后想到了一个新的问题，问题如下：

有一个长度为$n$的整数序列$a$，其中序列中的第$i$个元素为$a_i$，序列中每一个元素可以被随意设置为$[1,m]$区间内的任意一个整数，问所有不同的序列$a$的$gcd(a_1,a_2,…,a_n)$的和是多少?

肖肖现在特别想知道这题答案，你能告诉他吗？

$GCD$：最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

$Note$：当两个序列，存在任意元素不同，或是元素顺序不同时，我们认为这两个序列是不同的。如：$[1,2,3]$与$[1,3,2]$，以及$[1,2,3]$与$[1,2,2]$我们都认为是不同的序列。而$[1,2,3]$与$[1,2,3]$我们认为是同一个序列。

Input Format

第一个行输入一个正整数$T(1 \leq T\leq10)$，表示共有$T$组测试样例。

对于每组测试样例：

输入一个行，包含两个正整数$n$，$m(2\leq n\leq 10^9,1\leq m\leq 10^6)$。

Output Format

对于每组样例，输出一行，包含一个正整数，表示答案。由于答案可能比较大，请输出答案对$10^9+7$取模后的结果。

2
2 2
2 3

5
12

Source

1816 Online Judge 10.100.0.232