Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Sereja asks you to find out number of arrays A of size N, i.e. A_{1}, A_{2}, ..., A_{N} (1 ≤ A_{i} ≤ M), such that for each pair i, j (1 ≤ i < j ≤ N) gcd(A_{i}, A_{j}) = 1. 

As the answer could be large, print it modulo 10^{9} + 7 (1000000007).

------ Input ------ 

First line of the input contain an integer T - number of test cases. 

T tests follow. First line of each test case contain two space separated integers N, M. 

------ Output ------ 

For each test case output required answer modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤  10 $
$1 ≤ N ≤  10^{5} $
$1 ≤ M ≤  100 $

------ Subtasks ------ 

$Subtask #1: (10 points, TL = 5 secs) 1 ≤ N, M ≤  10 $
$Subtask #2: (25 points, TL = 5 secs) 1 ≤ N ≤  100 $
$Subtask #3: (65 points, TL = 5 secs) original$

------ Example ------ 

Input:
2
1 1
3 3

Output:
1
13

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Combinatorics

Number theory

Dynamic programming

Mathematics


Solutions:
factors = [set(), set(), {2}, {3}, {2}, {5}, {2, 3}, {7}, {2}, {3}, {2, 5}, {11}, {2, 3}, {13}, {2, 7}, {3, 5}, {2}, {17}, {2, 3}, {19}, {2, 5}, {3, 7}, {2, 11}, {23}, {2, 3}, {5}, {2, 13}, {3}, {2, 7}, {29}, {2, 3, 5}, {31}, {2}, {11, 3}, {17, 2}, {5, 7}, {2, 3}, {37}, {2, 19}, {3, 13}, {2, 5}, {41}, {2, 3, 7}, {43}, {2, 11}, {3, 5}, {2, 23}, {47}, {2, 3}, {7}, {2, 5}, {17, 3}, {2, 13}, {53}, {2, 3}, {11, 5}, {2, 7}, {19, 3}, {2, 29}, {59}, {2, 3, 5}, {61}, {2, 31}, {3, 7}, {2}, {13, 5}, {11, 2, 3}, {67}, {17, 2}, {3, 23}, {2, 5, 7}, {71}, {2, 3}, {73}, {2, 37}, {3, 5}, {2, 19}, {11, 7}, {2, 3, 13}, {79}, {2, 5}, {3}, {41, 2}, {83}, {2, 3, 7}, {17, 5}, {2, 43}, {3, 29}, {2, 11}, {89}, {2, 3, 5}, {13, 7}, {2, 23}, {3, 31}, {2, 47}, {19, 5}, {2, 3}, {97}, {2, 7}, {11, 3}, {2, 5}]
mod = 10 ** 9 + 7
memo = {}

def half(m, banned=set()):
	banned = {x for x in banned if x <= m}
	if m == 1:
		return [1]
	key = (m, tuple(sorted(banned)))
	if key not in memo:
		size = [0] * (m + 1)
		for (i, j) in enumerate(half(m - 1, banned)):
			size[i] += j
		f = factors[m]
		if max(f) <= 50 and (not f & banned):
			for (i, j) in enumerate(half(m - 1, banned | f)):
				size[i + 1] += j
		memo[key] = size
	return memo[key]
q = [1]
for i in range(1, 100001):
	q.append(q[-1] * i % mod)
inv = [pow(i, mod - 2, mod) for i in q]
A = lambda k, n: q[n] * inv[n - k] % mod
C = lambda k, n: q[n] * inv[n - k] * inv[k] % mod

def bigger(m):
	big = sum((i <= m for i in [53, 59, 61, 67, 71, 73, 79, 83, 89, 97]))
	ans = [0] * (m + 1)
	v = half(m)
	for i in range(m + 1):
		for j in range(big + 1):
			if i + j <= m:
				ans[i + j] += v[i] * C(j, big)
				ans[i + j] %= mod
	return ans

def solve(n, m):
	ans = bigger(m) if m > 50 else half(m)
	r = 0
	for (i, j) in enumerate(ans):
		if i <= n and j:
			r += A(i, n) * j % mod
			r %= mod
	return r
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(solve(n, m))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m
mod = 10 ** 9 + 7
maxM = 100
p = [False, False] + [True for _ in range(maxM - 1)]
fact = [[] for _ in range(maxM + 1)]
for i in range(2, maxM + 1):
	if p[i]:
		for j in range(1, maxM // i + 1):
			if j > 1:
				p[i * j] = False
			fact[i * j].append(i)
inv_fact = {}
for i in range(maxM + 1):
	for f in fact[i]:
		if not f in inv_fact:
			inv_fact[f] = set()
		inv_fact[f].add(i)
F = [1]
for i in range(1, 10 ** 5 + 1):
	F.append(F[-1] * i % mod)
mod_inv_F = list(map(lambda x: modinv(x, mod), F))

def g(n, k):
	return F[n] * mod_inv_F[n - k] % mod

def h(nums):
	hsh = []
	alias = {}
	i = 0
	for n in nums:
		for f in fact[n]:
			if not f in alias:
				alias[f] = i
				i += 1
		hsh.append(tuple(map(lambda x: alias[x], fact[n])))
	return tuple(sorted(hsh))
cache = {}

def get_lens(n, available, l):
	res = g(n, l)
	if n == l or len(available) == 0:
		return res
	hsh = (n, l, h(available))
	if hsh in cache:
		return cache[hsh]
	for a in available:
		acopy = set(available)
		for f in fact[a]:
			acopy -= inv_fact[f]
		for el in available:
			if el >= a and el in acopy:
				acopy.remove(el)
		res += get_lens(n, acopy, l + 1)
		res %= mod
	cache[hsh] = res
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(get_lens(n, set(range(2, m + 1)), 0))


import sys
import numpy as np

def memo(f):
	D = dict()

	def g(*a):
		try:
			return D[a]
		except:
			x = f(*a)
			D[a] = x
			return x
	return g
NMAX = 100
MMAX = 10 ** 5
mod = 10 ** 9 + 7

def gcd2(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = gcd2(b % a, a)
		return (g, x - b // a * y, y)

def inv(a):
	return gcd2(a, mod)[1] % mod
primeB = np.ones(NMAX + 1, dtype=bool)
primeB[0] = primeB[1] = False
for q in range(2, NMAX + 1):
	if primeB[q]:
		primeB[q * 2::q] = False
P = np.where(primeB)[0]
sfree = np.ones(NMAX + 1, dtype=np.int64)
sfree[0] = 0
for p in P:
	sfree[p::p] *= p
sbits = np.zeros(NMAX + 1, dtype=np.int64)
for (i, p) in enumerate(P):
	sbits[p::p] |= 1 << i
F = np.ones(MMAX + 1, dtype=np.int64)
G = np.ones(MMAX + 1, dtype=np.int64)
for x in range(1, MMAX + 1):
	F[x] = F[x - 1] * x % mod
	G[x] = G[x - 1] * inv(x) % mod

def choose(n, k):
	return F[n] * G[n - k] % mod * G[k] % mod

def solve(n, m):
	Q = P[P <= m]
	Q0 = Q[Q * 2 > m]
	Q = Q[Q * 2 <= m]
	lq = len(Q)
	D = np.zeros((2 ** lq, lq + 1), dtype=np.int64, order='F')
	alq = np.arange(2 ** lq)
	D[0, 0] = 1
	for i in range(2, m + 1):
		if i * 2 > m and primeB[i]:
			continue
		si = sbits[i]
		for x in range(min(lq - 1, i), -1, -1):
			g0 = np.where(alq & si == 0)[0]
			g0 = g0[D[g0, x] > 0]
			D[g0 + si, x + 1] += D[g0, x]
			D[g0 + si, x + 1] %= mod
	ret = 0
	nbig = len(Q0)
	for i in range(0, lq + 1):
		if i <= n:
			ss = np.sum(D[:, i]) % mod
			for j in range(nbig + 1):
				ij = i + j
				if ij <= n:
					s = ss * choose(nbig, j) % mod
					mult = choose(n, ij) * F[ij] % mod
					ret += mult * s
					ret %= mod
	return ret
f = sys.stdin
q = int(f.readline())
for i in range(q):
	print(solve(*map(int, f.readline().split())))