Suppose we have an n-dimensional supercomputer with an infinite number of processors. Every processor has a vector of $n$ integers as its (n-dimensional) coordinates and can be thought of as a point in the $n$-dimensional space. Furthermore, at every $n$-dimensional lattice point, there is a processor. Two processors are called neighbors if their coordinate vectors are different in only one position, and the absolute difference of the numbers in that position is equal to ${1}$. For example $(0,0,0)$ and $(1,0,0)$ are neighbors, and so are $(-1,2,3,4)$ and $(-1,2,3,3)$. But $(0,0,0)$ and $(1,0,1)$, and $(1,2,3,4)$ and $(1,2,3,2)$, are not neighbors.

Some processors of this computer are infected by a virus. At time ${0}$, only one processor is infected. After every second, all uninfected processors that are neighbors with infected ones become infected too. Given $n$ and ${t}}$, calculate the number of processors that are infected after ${t}$ seconds, modulo $(10^9+7)$.

Input Format

The first line contains an integer ${Q}$, the number of test cases. 

Each of the next ${Q}$ lines contains two integers $n$ and $\boldsymbol{\boldsymbol{t}}$, separated by a space.

Output Format

For every test case, write the answer in a single line.  

Constraints  

$1\leq Q\leq10^5$ 

$1\leq n\leq5\times10^6$ 

$0\leq t\leq10^{18}$ 

The sum of all $n$'s in one file does not exceed $5\times10^{6}$

Sample Input
5
2 0
2 1
2 2
3 1
1 10

Sample Output
1
5
13
7
21

Explanation

Source: hackerrank | Difficulty: HARD
Tags: Number theory


Solutions:
import sys
mod = 10 ** 9 + 7
L = 5000011
x = [1] * L
for i in range(2, L):
	x[i] = (mod - mod // i) * x[mod % i] % mod
for i in range(1, L):
	x[i] = 2 * x[i] * x[i] % mod
for cas in range(int(sys.stdin.readline())):
	(a, b) = map(int, sys.stdin.readline().strip().split())
	a += 1
	b += 1
	m = min(a, b)
	a %= mod
	b %= mod
	t = p = 1
	for i in range(1, m):
		p *= (a - i) * (b - i) % mod * x[i]
		p %= mod
		if p == 0:
			break
		t += p
	print(t % mod)


import sys
mod = 10 ** 9 + 7
L = 5000011
x = [1] * L
for i in range(2, L):
	x[i] = (mod - mod // i) * x[mod % i] % mod
for i in range(1, L):
	x[i] = 2 * x[i] * x[i] % mod
for cas in range(int(sys.stdin.readline())):
	(a, b) = map(int, sys.stdin.readline().strip().split())
	a += 1
	b += 1
	m = min(a, b)
	a %= mod
	b %= mod
	t = p = 1
	for i in range(1, m):
		p *= (a - i) * (b - i) % mod * x[i]
		p %= mod
		if p == 0:
			break
		t += p
	print(t % mod)