Chef is playing a game on the non-negative x-axis. It takes him $1$ second to reach from $i^{th}$ position to $(i-1)^{th}$ position or $(i+1)^{th}$ position. The chef never goes to the negative x-axis. Also, Chef doesn't stop at any moment of time.
The movement of chef can be described as follows.
- At the start he is standing at $x=0$ at time $0$.
- In the first round, he moves towards $x=1$ and comes back to the $x=0$ position. 
- In the second round, he moves towards the $x=2$ and comes back again to $x=0$. 
- Generalizing, in the $k^{th}$ round, he moves from $x=0$ to $x=k$ and then returns back to $x=0$ at the end of the round. This goes on as the game progresses.
For Example, the path of Chef for $3^{rd}$ round is given below.
$0 - 1 - 2 - 3 - 2 - 1 - 0$ 
The overall path followed by Chef would look somewhat like this:
$0 - 1 - 0 - 1 - 2 - 1 - 0 - 1 - 2 - 3 - 2 - 1 - 0 - 1 - 2 - 3 - 4 - 3 - …$
You are given two non-negative integers $N$ and $K$. You have to tell the time at which Chef arrives at $x=N$ for the $K^{th}$ time. 
Note - Chef can not skip a position while visiting the positions.

-----Input:-----
- The first line contains $T$ the number of test cases. Then the test cases follow.
- Each test case contains a single line of two integers $N$ and $K$.

-----Output:-----
For each test case, print a single line containing one integer -- the time taken by the chef to arrive at $x=N$ for the $K^{th}$ time by modulo $1,000,000,007$.

-----Constraints-----
- $1 \le T \le 10^5$
- $0 \le N \le 10^9$
- $1 \le K \le 10^9$

-----Sample Input:-----
5
0 1
1 1
2 1
1 3
4 6

-----Sample Output:-----
0
1
4
5
46

-----Explanation:-----
Test Case 1:

Chef starts the journey from the $N = 0$ at time $t = 0$ and it's the first time $(K = 1)$, he is here. So, the answer is $0$.  
Test Case 2:

Chef starts the journey from the $N = 0$ at time $t = 0$ then goes to $N = 1$ at $t = 1$ and it's the first time $(K = 1)$, he is here. So, the answer is $1$.
Test Case 4:

The path followed by Chef to reach $1$ for the third time is given below.
$0 - 1 - 0 - 1 - 2 - 1$

He reaches $1$ for the third time at $t=5$.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
from random import choice, randint
inp = sys.stdin.readline
out = sys.stdout.write
flsh = sys.stdout.flush
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def MI():
	return map(int, inp().strip().split())

def LI():
	return list(map(int, inp().strip().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]

def LI_():
	return [int(x) - 1 for x in inp().strip().split()]

def LF():
	return [float(x) for x in inp().strip().split()]

def LS():
	return inp().strip().split()

def I():
	return int(inp().strip())

def F():
	return float(inp().strip())

def S():
	return inp().strip()

def pf(s):
	return out(s + '\n')

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	from math import ceil
	t = I()
	l = []
	for _ in range(t):
		(n, k) = MI()
		if n == 0:
			k -= 1
			ans = k * (k + 1) % mod
			l.append(ans)
		elif k % 2 != 0:
			lr = k // 2
			l.append((n * n % mod + lr * (2 * n % mod) % mod + lr * (lr + 1) % mod) % mod)
		else:
			lr = k // 2
			l.append((n * n % mod + lr * (2 * n) % mod % mod + lr * (lr - 1) % mod) % mod)
	for i in range(t):
		pf(str(l[i]))

def __starting_point():
	main()
__starting_point()


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	if n == 0 and k == 1:
		print(0)
	elif n == 0:
		print(k * (k - 1) % q)
	else:
		m = n + 1
		q = 10 ** 9 + 7
		if k % 2 == 0:
			m += k // 2 - 1
			print((m ** 2 + n - m) % q)
		else:
			m += (k + 1) // 2 - 1
			print((m ** 2 - n - m) % q)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	if n == 0:
		print(k * (k - 1) % 1000000007)
	elif k == 1:
		print(n ** 2 % 1000000007)
	else:
		turn = k // 2
		point = turn + n
		if k % 2 == 0:
			print((point ** 2 - turn) % 1000000007)
		else:
			print((point ** 2 + turn) % 1000000007)


try:
	t = int(input())
	for _ in range(t):
		(a, b) = map(int, input().split())
		if a == 0:
			print((b - 1) * b % 1000000007)
		else:
			c = b % 2
			if c == 0:
				x = (b - 2) // 2
				ans = (a + x) * (a + x + 1) + a
				print(ans % 1000000007)
			else:
				x = b // 2
				ans = (a + x - 1) * (a + x)
				ans = ans + a + 2 * x
				print(ans % 1000000007)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = 10 ** 9 + 7
	if n == 0:
		if k == 1:
			print(0)
		else:
			print(k * (k - 1) % m)
	elif k == 1:
		print((n * (n - 1) + n) % m)
	elif k % 2:
		x = n + (k - 1) // 2
		print((x * (x + 1) - n) % m)
	else:
		x = n + k // 2
		print((x * (x - 1) + n) % m)


t = int(input().strip())
m = 1000000007
for _ in range(t):
	(n, k) = [int(x) for x in input().strip().split()]
	if n == 0:
		ans = k * (k - 1) % m
	elif k % 2 == 0:
		ans = (n * n % m + k * n % m + k * (k - 2) // 4 % m) % m
	else:
		ans = (n * n % m + (k - 1) * n % m + (k + 1) * (k - 1) // 4 % m) % m
	print(ans)


try:
	t = int(input())
	for _ in range(t):
		(x, y) = map(int, input().split())
		if x == 0:
			print((y - 1) * y % 1000000007)
		else:
			inc = y % 2
			if inc == 0:
				cir = (y - 2) // 2
				a = (x + cir) * (x + cir + 1) + x
				print(a % 1000000007)
			else:
				cir = y // 2
				a = (x + cir - 1) * (x + cir)
				a = a + x + 2 * cir
				print(a % 1000000007)
except:
	pass


for t in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	if n == 0:
		if k == 1:
			print(0)
		else:
			print(k * (k - 1) % mod)
	elif k % 2 == 0:
		a = n + k // 2 - 1
		print((a * (a + 1) + n) % mod)
	else:
		a = n + k // 2
		print((a * (a + 1) - n) % mod)


from bisect import bisect_left as bl, bisect_right as br
from collections import defaultdict as dd
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = list(map(int, input().strip().split()))
	if k == 1:
		sm = pow(n, 2, mod)
		print(sm)
		continue
	elif n == 0:
		sm = k * (k - 1)
		print(sm % mod)
		continue
	else:
		sm = n * (n + 1) % mod
	y = (k - 1) / 2
	q = y
	if int(y) == y:
		y = max(0, int(y) - 1)
		rem = 2
	else:
		y = int(y)
		rem = 1
	sm += 2 * y * n % mod + y * (y + 1) % mod
	if rem == 1:
		sm += n
	else:
		sm += 2 * (n + y + 1) - n
	print(sm % mod)


md = 1000000007
for tst in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if n == 0:
		ans = k * (k - 1) % md
		print(ans)
		continue
	z = 0
	if k & 1:
		z = 1
	g = k // 2 + n
	ans = (g + 1) * g
	if z:
		ans = (ans - n) % md
	else:
		ans = (ans - g - g + n) % md
	print(ans)


try:
	t = int(input())
	for _ in range(t):
		(a, b) = map(int, input().split())
		if a == 0:
			print((b - 1) * b % 1000000007)
		else:
			inc = b % 2
			if inc == 0:
				cir = (b - 2) // 2
				ans = (a + cir) * (a + cir + 1) + a
				print(ans % 1000000007)
			else:
				cir = b // 2
				ans = (a + cir - 1) * (a + cir)
				ans = ans + a + 2 * cir
				print(ans % 1000000007)
except:
	pass


for i in range(int(input())):
	(n, k) = map(int, input().split())
	if n != 0:
		d = (k - 1) // 2
		z = n ** 2 + k // 2 * (2 * n) + d * (d + 1)
		z = z % (10 ** 9 + 7)
		print(z)
	else:
		z = k * (k - 1)
		z = z % (10 ** 9 + 7)
		print(z)


import math
mod = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(N, K) = list(map(int, input().split()))
	if N == 0:
		print(K * (K - 1) % mod)
	else:
		pos = math.ceil((K - 1) / 2) + N
		if K % 2 == 0 or K == 1:
			et = N
		else:
			et = pos + pos - N
		t = (pos * (pos - 1) + et) % mod
		print(t % mod)


t = int(input())
for hh in range(0, t):
	(n, k) = [int(x) for x in input().split()]
	m = 1000000007
	pos = n
	if n == 0:
		rem = k - 1
		cur = rem * (rem + 1) % m
		print(cur)
	elif k == 1:
		prev = pos * (pos - 1) % m
		curr = (prev + pos) % m
		print(curr)
	elif k % 2 == 1:
		k -= 1
		p = k // 2
		ans = 2 * pos
		inipos = pos
		pos = (pos + p - 1) % m
		prev = pos * (pos + 1) % m
		now = (inipos + p) % m
		rem = (now - inipos + m) % m
		curr = (prev + now + rem) % m
		print(curr)
	else:
		k -= 1
		p = k // 2
		inipos = pos
		pos = (pos + p) % m
		prev = pos * (pos + 1) % m
		curr = (prev + inipos) % m
		print(curr)


t = int(input())
M = 1000000007
for z in range(t):
	(N, K) = list(map(int, input().split()))
	if N == 0:
		K = K - 1
		t = K * (K + 1) % M
		print(t)
		continue
	if K % 2 == 0:
		s = N + K // 2 - 1
		t = (s * (s + 1) % M + N) % M
	else:
		s = N + K // 2
		t = (s * (s + 1) % M - N) % M
	print(t)


from math import *
t = int(input())
p = 1000000007
while t:
	t -= 1
	(x, k) = list(map(int, input().split()))
	y = ceil(k / 2)
	if x == 0:
		if k == 1:
			print(0)
			continue
		k -= 1
		y = k * (k + 1)
		y = y // 2
		y = y * 2
		print(y % p)
		continue
	if k == 1:
		print(x * x % p)
	elif k == 2:
		z = x * x
		z += 2 * x
		print(z % p)
	elif k % 2:
		minus = x * (x + 1)
		minus = minus // 2
		fi = x * x
		y = x + k // 2
		fac = y * (y + 1) // 2
		fac -= minus
		fac = fac * 2
		fi += fac
		print(fi % p)
	else:
		minus = x * (x + 1)
		minus = minus // 2
		se = x * x + 2 * x
		y = x + (k - 1) // 2
		fac = y * (y + 1) // 2
		fac -= minus
		fac = fac * 2
		se += fac
		print(se % p)


from math import *
t = int(input())
p = 10 ** 9 + 7
for i in range(t):
	(n, k) = list(map(int, input().split()))
	ans = (n + ceil((k - 1) / 2)) % p
	r = ans
	ans = (ans + 1) * ans // 2 * 2 % p
	if k == 0:
		print(0)
		continue
	k = k - 1
	if n == 0:
		print(k * (k + 1) // 2 * 2 % p)
		continue
	if k != 0:
		if k % 2 == 0:
			ans = ans - (r - (r - n))
		else:
			ans = ans - r - (r - n)
	else:
		ans = ans - r
	print(ans % p)


t = int(input())
for i in range(t):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	if a == 0:
		b = b * 2
	ans = pow(a, 2) + int(b / 2) * 2 * a + pow(int(b / 2) - 1, 2) + int(b / 2) - 1
	if b % 2 != 0:
		ans = ans + b - 1
	print(ans % 1000000007)


def solve(n, k):
	ans = 0
	if n == 0:
		if k == 1:
			return 0
		else:
			ans = (k - 1) * k
			return ans % 1000000007
	if k == 1:
		return n * n % 1000000007
	if k % 2 == 0:
		ans = n * n + n * k + int(int((k - 1) / 2) * int((k - 1) / 2 + 1))
	if k % 2 != 0:
		ans = n * n + 2 * n * max(0, int((k - 1) / 2)) + int(int((k - 1) / 2) * int((k - 1) / 2 + 1))
	return ans % 1000000007
t = int(input())
for qw in range(t):
	(n, k) = list(map(int, input().split()))
	print(solve(n, k))


import math
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	t = math.floor(k / 2)
	r = n + t
	s = r * (r + 1)
	if k % 2 == 1:
		s -= n
	else:
		s = s - r
		s = s - t
	if n == 0:
		k = k - 1
		s = int(k * (k + 1))
	print(s % 1000000007)


import sys
msg = sys.stdin.readlines()
l = []
for i in msg:
	l.append(list(map(int, i.split())))
sm = lambda x: int(x * (x + 1) * 1)

def timew(n, k):
	if n == 0:
		time = sm(k - 1)
	elif k == 1:
		time = (n - 1) * n + n
	elif k % 2 == 1:
		pre_rounds = (k - 1) // 2
		time = sm(n + pre_rounds - 1) + n + 2 * pre_rounds
	else:
		pre_rounds = k // 2
		time = sm(n + pre_rounds - 1) + n
	return time % 1000000007
for i in l[1:]:
	[n, k] = i
	print(timew(n, k))


t = int(input())
while t:
	(n, k) = map(int, input().split())
	x = k // 2
	if n == 0:
		print(k * (k - 1) % 1000000007)
	elif k % 2 == 0:
		print(((n + x) * (n + x) - x) % 1000000007)
	else:
		print(((n + x) * (n + x) + x) % 1000000007)
	t -= 1