Sophia has discovered several alien languages. Suprisingly, all of these languages have an alphabet, and each of them may contain thousands of characters! Also, all the words in a language have the same number of characters in it.

However, the aliens like their words to be aesthetically pleasing, which for them means that for the $i^{th}$ letter of an $n$-letter alphabet (letters are indexed $1\ldots n$):

if $2i>n$, then the $i^{th}$ letter may be the last letter of a word, or it may be immediately followed by any letter, including itself.

if $2i\leq n$, then the $i^{th}$ letter can not be the last letter of a word and also can only be immediately followed by $j^{th}$ letter if and only if $j\geq2i$.  

Sophia wants to know how many different words exist in this language. Since the result may be large, she wants to know this number, modulo $100000007(10^8+7)$.

Input Format

The first line contains $\boldsymbol{\boldsymbol{t}}$, the number of test cases. The first line is followed by $\boldsymbol{\boldsymbol{t}}$ lines, each line denoting a test case. Each test case will have two space-separated integers $n$, $m$ which denote the number of letters in the language and the length of words in this language respectively.

Constraints

$1\leq t\leq5$  
$1\leq n\leq10^5$  
$1\leq m\leq5\cdot10^5$  

Output Format

For each test case, output the number of possible words modulo $100000007(10^8+7)$.

Sample Input
3
1 3
2 3
3 2

Sample Output
1
3
6

Explanation

For the first test case, there's one letter ('a') and all the words consist of $3$ letters. There's only one possibility which is "aaa".  

For the second test case, there are two letters ('a' and 'b') and all the words are of $3$ letters. The possible strings are "abb", "bab", & "bbb". The words can end only with 'b' because $2\cdot\text{index}(b)=2\cdot2>2$ and for 'a', it's $2\cdot\text{index}(a)=2\cdot1\leq2$. "aab" is not allowed because 'a' can not be followed immediately by 'a'. For a word of length 4 and alphabet of size 2, "abab" would be allowed.

For the third test case, there are three letters ('a', 'b' and 'c') and all of the words are $2$ letters. The words can only end with 'b' or 'c'. The possible words are "ab", "ac", "bb", "cc", "bc", "cb".

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


import os
import sys
mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


import os
import sys
mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


import os
import sys

def alienLanguages():
	mod = 10 ** 8 + 7
	for cas in range(int(input())):
		(n, m) = map(int, input().strip().split())
		v = [2 * i > n for i in range(n + 1)]
		for i in range(n - 1, -1, -1):
			v[i] += v[i + 1]
		c = []
		while v[1]:
			c.append(v[1])
			for i in range(1, n // 2 + 1):
				v[i] = v[2 * i]
			for i in range(n // 2 + 1, n + 1):
				v[i] = 0
			for i in range(n - 1, -1, -1):
				v[i] = (v[i] + v[i + 1]) % mod
		f = [1] + [0] * (len(c) - 1)
		for k in range(1, m + 1):
			f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
		print(f[0])
alienLanguages()


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


import math
import os
import random
import re
import sys
mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for daba in range(int(input())):
	(dinaa, madam) = map(int, input().strip().split())
	occurance = [2 * i > dinaa for i in range(dinaa + 1)]
	for i in range(dinaa - 1, -1, -1):
		occurance[i] += occurance[i + 1]
	c = []
	while occurance[1]:
		c.append(occurance[1])
		for i in range(1, dinaa // 2 + 1):
			occurance[i] = occurance[2 * i]
		for i in range(dinaa // 2 + 1, dinaa + 1):
			occurance[i] = 0
		for i in range(dinaa - 1, -1, -1):
			occurance[i] = (occurance[i] + occurance[i + 1]) % mod
	hanau = [1] + [0] * (len(c) - 1)
	for k in range(1, madam + 1):
		hanau = [sum((F * C for (F, C) in zip(hanau, c))) % mod] + hanau[:-1]
	print(hanau[0])


vvs = 10 ** 8 + 7
for kol in range(int(input())):
	(coco, pep) = map(int, input().strip().split())
	xx = [2 * r > coco for r in range(coco + 1)]
	for r in range(coco - 1, -1, -1):
		xx[r] += xx[r + 1]
	Q = []
	while xx[1]:
		Q.append(xx[1])
		for r in range(1, coco // 2 + 1):
			xx[r] = xx[2 * r]
		for r in range(coco // 2 + 1, coco + 1):
			xx[r] = 0
		for r in range(coco - 1, -1, -1):
			xx[r] = (xx[r] + xx[r + 1]) % vvs
	lol = [1] + [0] * (len(Q) - 1)
	for k in range(1, pep + 1):
		lol = [sum((F * C for (F, C) in zip(lol, Q))) % vvs] + lol[:-1]
	print(lol[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


output = 10 ** 8 + 7
for ven in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % output
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % output] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])


mod = 10 ** 8 + 7
for cas in range(int(input())):
	(n, m) = map(int, input().strip().split())
	v = [2 * i > n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		v[i] += v[i + 1]
	c = []
	while v[1]:
		c.append(v[1])
		for i in range(1, n // 2 + 1):
			v[i] = v[2 * i]
		for i in range(n // 2 + 1, n + 1):
			v[i] = 0
		for i in range(n - 1, -1, -1):
			v[i] = (v[i] + v[i + 1]) % mod
	f = [1] + [0] * (len(c) - 1)
	for k in range(1, m + 1):
		f = [sum((F * C for (F, C) in zip(f, c))) % mod] + f[:-1]
	print(f[0])