Alice jogs everyday to keep herself fit and active. She noticed that she burns X calories when jogging the first kilometer, and for K > 1, jogging the K^{th} kilometer burns calories equivalent to the total number of calories burned while jogging the first K-1 kilometers.

What is the total number of calories that Alice burns after jogging for N kilometers? The answer can be very large, so report it modulo 10^{9} + 7 (1000000007).

------ Input Format ------ 

- The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains two space-separated integers N and X, as described in the problem statement. 

------ Output Format ------ 

For each test case, output on a new line the total number of calories that Alice burns after jogging for N kilometers, modulo 10^{9} + 7.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{6}$
$1 ≤ X ≤ 100$

----- Sample Input 1 ------ 
3
1 2
2 1
12548 1

----- Sample Output 1 ------ 
2
2
588809226

----- explanation 1 ------ 
Test case $1$: Alice only jogs one kilometer, which burns $2$ calories since $X = 2$.

Test case $2$: Alice jogs two kilometers. The first burns $X = 1$ calorie, and the second also burns $1$ calorie since the total amount burnt before this is $1$ calorie. So, the total is $1 + 1 = 2$ calories burned.

Difficulty: MEDIUM
Tags: Preprocessing

Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = 0
	if n == 1:
		print(x)
	else:
		print(x * pow(2, n - 1, 10 ** 9 + 7) % (10 ** 9 + 7))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	c = 0
	a = pow(10, 9) + 7
	b = int(pow(2, n - 1, a) % a)
	print(int(b * x % a))


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


mod = 10 ** 9 + 7
for i in range(int(input())):
	(n, x) = map(int, input().split())
	print(pow(2, n - 1, mod) * x % mod)


for i in range(int(input())):
	m = 1000000007
	(n, x) = map(int, input().split())
	print(pow(2, n - 1, m) * x % m)


for _ in range(int(input())):
	(n, x) = [int(i) for i in input().split()]
	print(x * pow(2, n - 1, 10 ** 9 + 7) % (10 ** 9 + 7))


import math
s = 1000000007

def PowerOf2(a, n):
	(ans, x) = (1, a)
	while n != 0:
		if n & 1 == 1:
			ans = ans * x % s
		x = x * x % s
		n = n >> 1
	return ans % s
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	if n == 1:
		print(x)
	else:
		ans = PowerOf2(2, n - 1) - 1
		ans = ans * x % s
		ans = (ans + x) % s
		print(ans)


T = int(input())
for _ in range(T):
	(N, X) = map(int, input().split())
	print(pow(2, N - 1, 1000000007) * X % 1000000007)


tests = int(input())
for i in range(tests):
	(n, x) = map(int, input().split())
	ans = x * pow(2, n - 1, 1000000007) % 1000000007
	print(ans)


a = int(input())
for i in range(a):
	l = list(map(int, input().split()))
	c = 10 ** 9 + 7
	print(pow(2, l[0] - 1, c) * l[1] % c)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	if n == 1:
		print(x)
	else:
		ans = pow(2, n - 1, 1000000007) * x
		print(ans % 1000000007)


t = int(input())
for _ in range(t):
	a = input().split()
	n = int(a[0])
	x = int(a[1])
	if n > 1:
		summ = x * pow(2, n - 1, 1000000007) % 1000000007
		print(summ)
	else:
		print(x)


mod = 1000000007
T = int(input())
for i in range(T):
	(n, x) = map(int, input().split())
	print(pow(2, n - 1, mod) * x % mod)


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
from random import randint
import math
import sys
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	print(x * pow(2, n - 1, mod) % mod)


t = int(input())
while t > 0:
	(n, x) = map(int, input().split(' '))
	print(pow(2, n - 1, 1000000007) * x % 1000000007)
	t -= 1


def fastpower(b, e):
	ans = 1
	while e > 0:
		if e % 2 == 1:
			ans = ans * b % 1000000007
		b = b * b % 1000000007
		e = e // 2 % 1000000007
	return ans
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	q = x * fastpower(2, n - 1)
	print(q % 1000000007)


T = int(input())
for _ in range(T):
	(N, X) = map(int, input().split(' '))
	mod_val = 10 ** 9 + 7
	val = pow(2, N - 1, mod_val)
	ans = val * X % 1000000007
	print(ans)


def calc_fib(x, y):
	if x == 1:
		return y
	elif x > 1:
		x = x - 1
		z = pow(2, x, 1000000007)
		return z * y % 1000000007
n = int(input(''))
for i in range(n):
	(x, y) = map(int, input('').split())
	print(calc_fib(x, y))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	print(pow(2, n - 1, 1000000007) * x % 1000000007)


import math
t = int(input())
for i in range(0, t):
	(a, b) = map(int, input().split())
	print(pow(2, a - 1, 1000000007) * b % 1000000007)


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7
pow2 = [1] * int(1000000.0 + 5)
for i in range(1, len(pow2)):
	pow2[i] = pow2[i - 1] * 2 % M

def solve():
	(n, x) = map(int, input().split())
	return x * pow2[n - 1] % M
for _ in range(int(input())):
	print(solve())


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


mod = 10 ** 9 + 7
for i in range(int(input())):
	(N, X) = map(int, input().split())
	print(pow(2, N - 1, mod) * X % mod)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	n = 1000000007
	print(y * pow(2, x - 1, n) % n)


for i in range(int(input())):
	(N, X) = map(int, input().split())
	M = 1000000007
	print(X * pow(2, N - 1, M) % M)


def jogging(N, X):
	mod = 10 ** 9 + 7
	print(pow(2, N - 1, mod) * X % mod)
t = int(input())
for _ in range(t):
	(N, X) = map(int, input().split())
	jogging(N, X)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	mod = 1000000007
	if n == 1:
		print(x)
	else:
		print(pow(2, n - 1, mod) * x % mod)


from sys import stdin
from sys import stdout
T = int(stdin.readline())
for i in range(0, T):
	Z = list(map(int, stdin.readline().split()))
	N = Z[0]
	X = Z[1]
	M = 100000007
	if N == 1:
		ans = X
	elif N == 2:
		ans = 2 * X
	else:
		ans = pow(2, N - 1, 1000000007) * X
	print(ans % 1000000007)


t = int(input())
mod = 10 ** 9 + 7
while t > 0:
	t -= 1
	(n, x) = map(int, input().split())
	print(x * pow(2, n - 1, mod) % mod)


T = int(input())
for i in range(T):
	(N, X) = map(int, input().split())
	ans = pow(2, N - 1, 1000000007) * X
	print(ans % 1000000007)


def main():
	T = int(input())
	mod = 1000000007
	for _ in range(T):
		(N, X) = map(int, input().split())
		print(X % mod * pow(2, N - 1, mod) % mod)
main()


T = int(input())
myval = []
for t in range(T):
	NX = input().split()
	N = int(NX[0])
	X = int(NX[1])
	val = 0
	m = 1000000007
	val = X * pow(2, N - 1, m) % m
	myval.append(val)
for t in range(T):
	print(myval[t])


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(pow(2, a - 1, 1000000007) * b % 1000000007)


def findCalories(N, X):
	if N == 1:
		return 1 * X
	return pow(2, N - 1) % 1000000007 * X
T = int(input())
for testcase in range(T):
	(N, X) = list(map(int, input().split()))
	if N == 1:
		print(1 * X)
	else:
		print(pow(2, N - 1, 1000000007) * X % 1000000007)