Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef and his friend Bharat have decided to play the game "The Chefora Spell".

In the game, a positive integer N (in decimal system) is considered a "Chefora" if the number of digits d is odd and it satisfies the equation N = \sum_{i=0}^{d-1} N_{i} \cdot 10^{i},

where N_{i} is the i-th digit of N from the left in 0-based indexing.

Let A_{i} denote the i-th smallest Chefora number.

They'll ask each other Q questions, where each question contains two integers L and R. The opponent then has to answer with

(\prod_{i=L+1}^R (A_{L})^{A_{i}}) \bmod{10^{9}+7}.

Bharat has answered all the questions right, and now it is Chef's turn. But since Chef fears that he could get some questions wrong, you have come to his rescue!

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

- The first line contains an integer Q - the number of questions Bharat asks.
- Each of the next Q lines contains two integers L and R.

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

Print Q integers - the answers to the questions on separate lines.

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

$1 ≤ Q ≤ 10^{5}$
$1 ≤ L < R ≤ 10^{5}$

------ subtasks ------ 

Subtask #1 (30 points):
$1 ≤ Q ≤ 5 \cdot 10^{3}$
$1 ≤ L < R ≤ 5 \cdot 10^{3}$

Subtask #2 (70 points): Original constraints

----- Sample Input 1 ------ 
2
1 2
9 11
----- Sample Output 1 ------ 
1
541416750
----- explanation 1 ------ 
- For the first question:
$$(A_{1})^{A_{2}}=1^{2}=1.$$

- For the second question:
$$(A_{9})^{A_{10}}\cdot (A_{9})^{A_{11}}=9^{101}\cdot 9^{111}\equiv 541416750 \pmod{10^{9}+7}.$$

Difficulty: MEDIUM_HARD
Tags: Number theory

Preprocessing

Mathematics

Starter code:

Solutions:
def chefora(c):
	a = list(str(c))
	a = a + a[-2::-1]
	b = int(''.join(a))
	return b
l1 = [0]
for i in range(1, 100001):
	l1.append(chefora(i))
	l1[i] += l1[i - 1]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	ans = 0
	t = chefora(l)
	ans = l1[r] - l1[l]
	print(pow(t, ans, 1000000007))


try:

	class xyz:

		def __init__(self, n):
			self.n = n
			self.i = 0
			self.palin = [0] * n
			self.prefix = [0] * n

		def add(self, v):
			self.palin[self.i] = v
			self.prefix[self.i] = v
			if self.i != 0:
				self.prefix[self.i] += self.prefix[self.i - 1]
			self.i = self.i + 1

		def fill(self):
			return self.i == self.n

		def rangedprefix(self, l, r):
			return self.prefix[r] - self.prefix[l]

		def basepalindrome(self, l):
			return self.palin[l]

	def addpalindrome(a):
		n = a
		pal = a
		n = n // 10
		while n > 0:
			pal = pal * 10 + n % 10
			n = n // 10
		return pal

	def makepalin(palin):
		i = 1
		while not palin.fill():
			palin.add(addpalindrome(i))
			i += 1

	def calculate(l, r, palin):
		power = palin.rangedprefix(l - 1, r - 1)
		base = palin.basepalindrome(l - 1)
		return pow(base, power, 1000000007)
	palin = xyz(100001)
	makepalin(palin)
	r = int(input())
	while r > 0:
		(l, r) = map(int, input().split())
		print(calculate(l, r, palin))
		r -= 1
except:
	pass


try:

	def findpower(base, power):
		mod = 10 ** 9 + 7
		res = 1
		while power != 0:
			if power % 2 == 0:
				base = base % mod * (base % mod) % mod
				power = power // 2
			else:
				res = res % mod * (base % mod) % mod
				power = power - 1
		return res

	def findchefora(num):
		palin = num
		num = num // 10
		while num > 0:
			palin = palin * 10 + num % 10
			num = num // 10
		return palin
	arr = [0] * (10 ** 5 + 1)
	arrsm = [0] * (10 ** 5 + 1)
	for i in range(1, 10 ** 5 + 1):
		arr[i] = findchefora(i)
		arrsm[i] = arrsm[i - 1] + arr[i]
	for _ in range(int(input())):
		(l, r) = map(int, input().split())
		power = arrsm[r] - arrsm[l]
		print(findpower(arr[l], power))
except:
	pass


def binpov(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res
chefora = []
chefora.append(0)
for i in range(1, 100001):
	res = i
	num = i // 10
	while num != 0:
		res = res * 10 + num % 10
		num = num // 10
	chefora.append(res)
sub_sum = []
sum1 = 0
sub_sum.append(0)
length = len(chefora)
for i in range(1, length):
	sum1 += chefora[i]
	sub_sum.append(sum1)
t = int(input())
for z in range(t):
	(l, r) = map(int, input().split())
	A = chefora[l]
	print(binpov(A, sub_sum[r] - sub_sum[l], 1000000007))


try:

	class Palin:

		def __init__(self, n):
			self.n = n
			self.i = 0
			self.palin = [0] * n
			self.prefix = [0] * n

		def add(self, v):
			self.palin[self.i] = v
			self.prefix[self.i] = v
			if self.i != 0:
				self.prefix[self.i] += self.prefix[self.i - 1]
			self.i = self.i + 1

		def fill(self):
			return self.i == self.n

		def rangedPrefix(self, l, r):
			return self.prefix[r] - self.prefix[l]

		def basePalindrome(self, l):
			return self.palin[l]

	def oddPalindrome(a):
		n = a
		pal = a
		n = n // 10
		while n > 0:
			pal = pal * 10 + n % 10
			n = n // 10
		return pal

	def makePalin(palin):
		i = 1
		while not palin.fill():
			palin.add(oddPalindrome(i))
			i += 1

	def calculate(l, r, palin):
		power = palin.rangedPrefix(l - 1, r - 1)
		base = palin.basePalindrome(l - 1)
		return pow(base, power, 1000000007)
	palin = Palin(100001)
	makePalin(palin)
	t = int(input())
	while t > 0:
		(l, r) = map(int, input().split())
		print(calculate(l, r, palin))
		t -= 1
except:
	pass


mod = 10 ** 9 + 7
ans = [a for a in range(1, 10)]
for x in range(1, 10001):
	s = str(x)
	for y in range(10):
		ans.append(int(s + str(y) + s[::-1]))
pre = [0] * len(ans)
pre[0] = 0
for i in range(1, len(ans)):
	pre[i] = pre[i - 1] + ans[i - 1]

def power(a, b):
	res = 1
	a = a % mod
	while b > 0:
		if b % 2 == 1:
			res = res * a % mod
		b = b // 2
		a = a * a % mod
	return res
for testcase in range(int(input())):
	(l, r) = map(int, input().split())
	print(power(ans[l - 1], pre[r] - pre[l]))


def getpow(a, b):
	res = 1
	m = 10 ** 9 + 7
	while b >= 1:
		if b % 2:
			res = res % m * (a % m) % m
			b -= 1
		a = a % m * (a % m) % m
		b = b // 2
	return res

def getchf(n):
	st = str(n)
	st1 = st[-2::-1]
	st = st + st1
	return int(st)
chfarr = [0]
prfsum = [0]
for i in range(1, 100001):
	chfarr.append(getchf(i))
	prfsum.append(prfsum[i - 1] + chfarr[i])
q = int(input())
for i in range(0, q):
	(l, r) = map(int, input().split())
	res = 1
	res = getpow(chfarr[l], prfsum[r] - prfsum[l])
	print(res)


chefora = [1, 2, 3, 4, 5, 6, 7, 8, 9]
m = 10 ** 9 + 7

def rev(N):
	rm = str(N)[::-1]
	return rm
for i in range(1, 10 ** 4 + 1):
	for j in range(10):
		chefora.append(int(str(i) + str(j) + str(rev(i))))
presum = [0 for i in range(len(chefora))]
presum[0] = chefora[0]
for i in range(1, len(chefora)):
	presum[i] = presum[i - 1] + chefora[i]

def exp(a, b):
	rem = 1
	while b > 0:
		if b % 2 == 1:
			rem = rem * a % m
		a = a * a % m
		b = b // 2
	return rem % m
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	ans = exp(chefora[L - 1], presum[R - 1] - presum[L - 1])
	print(ans)


Q = int(input())
arr = []
arr.append(0)
for i in range(1, 10 ** 5 + 1):
	temp = i
	num = i // 10
	while num > 0:
		rem = num % 10
		temp = temp * 10 + rem
		num = num // 10
	arr.append(temp)
sm = []
sm.append(0)
for i in range(1, 10 ** 5 + 1):
	sm.append(sm[i - 1] + arr[i])

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
mod = 1000000007
while Q != 0:
	(l, r) = map(int, input().split())
	res = 1
	prefix = sm[r] - sm[l]
	base = arr[l]
	print(power(base, prefix, mod))
	Q -= 1


from math import ceil, gcd
MOD = 10 ** 9 + 7
inp = lambda x: map(int, x.split())

def find_oddn(l):
	(s, s1) = (str(l), list(str(l))[:-1])
	s1.reverse()
	s1 = ''.join(s1)
	s += s1
	return int(s)
arr = [0] * (10 ** 5 + 1)
(lr, l1, r1) = ([], 10 ** 5, 0)
t = int(input())
for _ in range(t):
	(l, r) = inp(input())
	lr.append([l, r])
	(l1, r1) = (min(l1, l), max(r1, r))
s = 0
for i in range(l1, r1 + 1):
	s += find_oddn(i)
	arr[i] = s
for _ in range(t):
	(l, r) = lr[_]
	a_l = arr[l] - arr[l - 1]
	v = a_l
	l_exp = [v]
	for i in range(50):
		v = v * v % MOD
		l_exp.append(v)
	s = arr[r] - arr[l]
	b = list(bin(s))[2:]
	b.reverse()
	(ans, l) = (1, len(b))
	for i in range(l):
		if b[i] == '1':
			ans *= l_exp[i]
	print(ans % MOD)


chf = []
for i in range(100001):
	if i >= 10:
		a = str(i)
		chf.append(int(str(i) + a[-2::-1]))
	else:
		chf.append(i)
prs = []
sm = 0
for x in chf:
	sm += x
	prs.append(sm)
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(pow(chf[l], prs[r] - prs[l], 10 ** 9 + 7))


def power(base, power):
	mod = 10 ** 9 + 7
	res = 1
	while power != 0:
		if power % 2 == 0:
			base = base % mod * (base % mod) % mod
			power = power // 2
		else:
			res = res % mod * (base % mod) % mod
			power = power - 1
	return res

def rev(a):
	b = a
	b = b // 10
	while b > 0:
		a = a * 10 + b % 10
		b = b // 10
	return a
t = int(input())
mod = 1000000007
c = [0] * (10 ** 5 + 1)
for i in range(1, 100001):
	c[i] = rev(i)
	c[i] = c[i] + c[i - 1]
while t > 0:
	(l, r) = map(int, input().split())
	s = c[r] - c[l]
	a = c[l] - c[l - 1]
	pro = power(a, s)
	pro = pro % mod
	print(pro)
	t = t - 1


j = [i for i in range(1, 10 ** 5 + 1)]
y = []
for i in j:
	r = i // 10
	if r == 0:
		y.append(i)
	else:
		u = str(i)
		h = str(r)
		y.append(int(u + h[::-1]))
z = y.copy()
for i in range(1, len(y)):
	y[i] += y[i - 1]
t = int(input())
while t > 0:
	(l, r) = map(int, input().split())
	ans = pow(z[l - 1], y[r - 1] - y[l - 1], 10 ** 9 + 7)
	print(ans)
	t -= 1


def findpower(base, power):
	mod = 10 ** 9 + 7
	res = 1
	while power != 0:
		if power % 2 == 0:
			base = base % mod * (base % mod) % mod
			power = power // 2
		else:
			res = res % mod * (base % mod) % mod
			power = power - 1
	return res

def findshefola(num):
	palindrome = num
	num = num // 10
	while num > 0:
		palindrome = palindrome * 10 + num % 10
		num = num // 10
	return palindrome
arr = [0] * (10 ** 5 + 1)
arrsm = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	arr[i] = findshefola(i)
	arrsm[i] = arrsm[i - 1] + arr[i]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	power = arrsm[r] - arrsm[l]
	print(findpower(arr[l], power))


class main:

	def __init__(self):
		self.mod = 1000000007

	def power(self, base, pow):
		pow = int(pow)
		res = 1
		while not pow == 0:
			if pow % 2 == 0:
				pow = int(pow / 2)
				base = int(base % self.mod * (base % self.mod) % self.mod)
			else:
				pow = pow - 1
				res = int(res % self.mod * (base % self.mod) % self.mod)
		return int(res)

	def chefora_num(self, i):
		if i < 10:
			return int(i)
		ch = str(int(i / 10))
		ch_0 = str(int(i % 10))
		res = ch + ch_0 + ch[::-1]
		return int(res)
C = main()
a = [0] * 100001
presum = [0] * 100001
for i in range(1, 100001):
	a[i] = C.chefora_num(i)
	presum[i] = presum[i - 1] + a[i]
q = int(input())
while q > 0:
	x = list(map(int, input().strip().split(' ')))
	(l, r) = (x[0], x[1])
	diff = presum[r] - presum[l]
	res = C.power(a[l], diff)
	print(res)
	q -= 1


class PalindromeAndPrefixSumEncapsulated:

	def __init__(self, n):
		self.n = n
		self.i = 0
		self.palindromes = [0] * n
		self.prefixSums = [0] * n

	def add(self, val):
		self.palindromes[self.i] = val
		self.prefixSums[self.i] = val
		if self.i != 0:
			self.prefixSums[self.i] += self.prefixSums[self.i - 1]
		self.i = self.i + 1

	def isFull(self):
		return self.i == self.n

	def getPrefixSumInRange(self, L, R):
		return self.prefixSums[R] - self.prefixSums[L]

	def getFirstPalin(self, index):
		return self.palindromes[index]

def createOddPalin(inp):
	n = inp
	palin = inp
	n = n // 10
	while n > 0:
		palin = palin * 10 + n % 10
		n = n // 10
	return palin

def generatePalindromes(palindromeAndPrefixSumEncapsulated):
	i = 1
	while not palindromeAndPrefixSumEncapsulated.isFull():
		palindromeAndPrefixSumEncapsulated.add(createOddPalin(i))
		i = i + 1

def solve(L, R, palindromeAndPrefixSumEncapsulated):
	power = palindromeAndPrefixSumEncapsulated.getPrefixSumInRange(L - 1, R - 1)
	base = palindromeAndPrefixSumEncapsulated.getFirstPalin(L - 1)
	return pow(base, power, 1000000007)
palindromeAndPrefixSumEncapsulated = PalindromeAndPrefixSumEncapsulated(100001)
generatePalindromes(palindromeAndPrefixSumEncapsulated)
q = int(input())
while q > 0:
	q = q - 1
	line = input().split(' ')
	(L, R) = (int(line[0]), int(line[1]))
	print(solve(L, R, palindromeAndPrefixSumEncapsulated))


sum_chefora = [1, 3, 6, 10, 15, 21, 28, 36, 45]
s = 45
count = 9
for i in range(2, 7):
	d = i - 1
	start = 10 ** (d - 1)
	end = -1 + 10 ** d
	for j in range(start, end + 1):
		for k in range(0, 10):
			if count == 100000:
				break
			temp = int(str(j) + str(k) + str(j)[::-1])
			s += temp
			sum_chefora.append(s)
			count += 1
		if count == 100000:
			break
	if count == 100000:
		break
q = int(input())
mod = 1000000007
for i in range(q):
	(l, r) = map(int, input().split())
	base = 0
	if l == 1:
		base = sum_chefora[0]
	else:
		base = sum_chefora[l - 1] - sum_chefora[l - 2]
	exponent = sum_chefora[r - 1] - sum_chefora[l - 1]
	print(pow(base, exponent, mod))


q = int(input())

def digits(n):
	d = 0
	while n:
		n = n // 10
		d += 1
	return d

def chefora(N):
	d = digits(N)
	temp = N // 10
	N = N * 10 ** (d - 1)
	for i in range(d - 1):
		N += temp % 10 * 10 ** (d - 2 - i)
		temp = temp // 10
	return N

def power(a, n):
	M = 1000000007
	res = 1
	while n:
		if n & 1:
			res = res * (a % M) % M
		n = n // 2
		a = a % M * (a % M) % M
	return res
chefsum = [0] * 100001
for i in range(1, 100001):
	chefsum[i] = chefsum[i - 1] + chefora(i)
for t in range(q):
	(L, R) = list(map(int, input().split(' ')))
	M = 1000000007
	s = (chefsum[R] - chefsum[L]) % (M - 1)
	print(power(chefora(L), s))


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
L = [0]
for i in range(1, 10 ** 5 + 1):
	x = i
	n = x // 10
	m = 0
	c = 0
	while n > 0:
		x = x * 10 + n % 10
		n = n // 10
		c += 1
	L.append(x)
mod = 10 ** 9 + 7
T = [0]
for i in range(1, 10 ** 5 + 1):
	T.append(L[i] + T[-1])
t = int(int(input()))
k = []
for test in range(t):
	(l, r) = map(int, input().split())
	x = T[r] - T[l]
	s = power(L[l], x, mod)
	k.append(s)
print(*k, sep='\n')


a = [0] * (10 ** 5 + 1)
a_sum = [0] * (10 ** 5 + 1)

def palindrome(num):
	result = num
	num //= 10
	while num > 0:
		result = result * 10 + num % 10
		num //= 10
	return result
for i in range(1, 10 ** 5 + 1):
	a[i] = palindrome(i)
	a_sum[i] = a_sum[i - 1] + a[i]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	result = 1
	power = a_sum[r] - a_sum[l]
	base = a[l]
	while power:
		if power % 2 == 0:
			base = base % (10 ** 9 + 7) * (base % (10 ** 9 + 7)) % (10 ** 9 + 7)
			power //= 2
		else:
			result = result % (10 ** 9 + 7) * (base % (10 ** 9 + 7)) % (10 ** 9 + 7)
			power -= 1
	print(result)


MOD = int(1000000000.0 + 7)
MX = int(100000.0 + 1)

def genChefora(L, R):
	chefora = []
	for i in range(L, R + 1):
		if i > 9:
			num = str(i)
			num += num[len(num) - 2::-1]
			num = int(num)
		else:
			num = i
		chefora.append(num)
	return chefora

def prefixSum(arr):
	ps = []
	ps.append(arr[0])
	for i in range(1, len(arr)):
		ps.append(arr[i] + ps[i - 1])
	return ps

def binPow(n, p):
	ans = 1
	n %= MOD
	while p:
		if p & 1:
			ans *= n % MOD
		n *= n % MOD
		p >>= 1
	return ans % MOD
cf = genChefora(1, MX)
pf = prefixSum(cf)
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	firstL = cf[L - 1]
	totalPow = pf[R - 1] - pf[L - 1]
	print(binPow(firstL, totalPow))


import math
import builtins
from itertools import accumulate
from sys import *

def countDigit(n):
	return math.floor(math.log10(n) + 1)
chefora = []
for i in range(1, 100001):
	if i < 10:
		chefora.append(i)
	else:
		c1 = countDigit(i)
		chefora.append(int(str(i) + str(i)[c1 - 2::-1]))
res = list(accumulate(chefora))
t = int(stdin.readline())
while t:
	line = stdin.readline().split(' ')
	(l, r) = (int(line[0]), int(line[1]))
	b = res[r - 1] - res[l - 1]
	a = chefora[l - 1]
	p = builtins.pow(a, b, 1000000007)
	print(p)
	t = t - 1


arr = []
for i in range(10):
	arr.append(i)
for i in range(10, pow(10, 5) + 1):
	arr.append(int(str(i) + str(i)[len(str(i)) - 2::-1]))
T = int(input())
sum_arr = []
s = 0
for j in arr:
	s += j
	sum_arr.append(s)
for i in range(T):
	(L, R) = map(int, input().split())
	print(pow(arr[L], sum_arr[R] - sum_arr[L], pow(10, 9) + 7))


mod = 10 ** 9 + 7

def reverse(n):
	m = n
	ans = m
	n = n // 10
	while n:
		rem = n % 10
		ans = ans * 10 + rem
		n = n // 10
	return ans

def mul(x, y):
	ans = x * y
	return ans % mod if ans > mod else ans

def exponential_power(a, b):
	if b < 0:
		return 1
	elif a == 0 or b == 1 or a == 1:
		return a % mod
	else:
		ans = 1
		a = a % mod
		while b:
			if b & 1:
				ans = mul(ans, a)
			a = mul(a, a)
			b = b >> 1
		return ans
arr = [reverse(i) for i in range(10 ** 5 + 5)]
prefix_sum = [0] * (10 ** 5 + 5)
for i in range(1, 10 ** 5 + 5):
	prefix_sum[i] = prefix_sum[i - 1] + arr[i]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	n = arr[l]
	ans = exponential_power(n, prefix_sum[r] - prefix_sum[l])
	print(ans)


mod = int(1000000000.0 + 7)

def chef(x):
	y = x // 10
	while y:
		x = x * 10 + y % 10
		y //= 10
	return x
lt = [0]
s = [0]
for i in range(1, 100001):
	lt.append(chef(i))
	s.append(lt[i] + s[i - 1])
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	ans = pow(lt[l], s[r] - s[l], mod)
	print(ans)


def odd_Palindrome(val):
	(n, palindrome) = (val, val)
	n //= 10
	while n > 0:
		palindrome = palindrome * 10 + n % 10
		n //= 10
	return palindrome

class Palin:

	def __init__(self, n):
		super(Palin, self).__init__()
		self.n = n
		self.i = 0
		self.palindrome = [0] * n
		self.prefix = [0] * n

	def fill(self):
		return self.i == self.n

	def add(self, v):
		self.palindrome[self.i] = v
		self.prefix[self.i] = v
		if self.i != 0:
			self.prefix[self.i] += self.prefix[self.i - 1]
		self.i = self.i + 1

	def basePalin(self, l):
		return self.palindrome[l]

	def rangedPrefix(self, l, r):
		return self.prefix[r] - self.prefix[l]

def create_Palin(palindrome):
	idx = 1
	while not palindrome.fill():
		palindrome.add(odd_Palindrome(idx))
		idx += 1

def calc(left, right, palindrome):
	power = palindrome.rangedPrefix(left - 1, right - 1)
	base = palindrome.basePalin(left - 1)
	return pow(base, power, 1000000007)

class Solution(object):
	try:
		obj_Palin = Palin(100001)
		create_Palin(obj_Palin)
		num_Of_Queries = int(input())
		while num_Of_Queries > 0:
			(left, right) = map(int, input().split())
			print(calc(left, right, obj_Palin))
			num_Of_Queries -= 1
	except Exception as e:
		raise e


summ = []
for ii in range(0, 10 ** 5 + 1):
	summ.append(0)
b1 = 0

def modu():
	return 10 ** 9 + 7

def p2(xx):
	return xx + 1

def p3(xx):
	if xx % 2 == 0:
		return True
	return False

def p4(xx):
	return xx // 2

def p5(a, b):
	return a % b
xxx = 0
x9 = 10 ** 5 + 1

def cal(b, p):
	a1 = 0
	mod = modu()
	res = 1
	l1 = []
	while p != 0:
		tempu = p3(p)
		if tempu:
			b = p5(b, mod) ** 2 % mod
			l1.append(b)
			p = p4(p)
			b1 = xxx
			l1.append(b1)
		else:
			xz = p5(res, mod)
			l1.append(xz)
			xz1 = p5(b, mod)
			res = xz * xz1 % mod
			l1.append(res)
			p -= 1
			a1 = xxx
	return res
arr = []
for ii in range(0, 10 ** 5 + 1):
	arr.append(0)
a1 = 0

def p1(xx):
	return xx // 10

def find(a):
	result = []
	temp = a
	a1 = xxx
	a = p1(a)
	while a > xxx:
		temp = temp * 10 + a % 10
		result.append(temp)
		a = p1(a)
		a1 = p2(a1)
		result.append(a1)
	return temp
tempyy = 0
t = []
for ii in range(0, x9):
	t.append(0)
for i in range(1, x9):
	yc = []
	arr[i] = find(i)
	yc.append(arr[i])
	res1 = 0
	summ[i] = summ[i - 1] + arr[i]
ttt = int(input())
for tt in range(0, ttt):
	inn = list(map(int, input().split()))
	l = inn[0]
	r = inn[1]
	ans = summ[r] - summ[l]
	res2 = ''
	out = cal(arr[l], ans)
	print(out)


import math
import itertools
from sys import stdin
from functools import reduce
from collections import deque
from sys import setrecursionlimit
from collections import defaultdict
import heapq
input = stdin.readline

def I():
	return int(input())

def IN():
	return map(int, input().split())

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

def LIN(N):
	return [list(map(int, input().split())) for _ in range(N)]
gcd = math.gcd
Inf = float('Inf')
a = [0] * (10 ** 5 + 1)
a_sum = [0] * (10 ** 5 + 1)

def palindrome(num):
	result = num
	num //= 10
	while num > 0:
		result = result * 10 + num % 10
		num //= 10
	return result
for i in range(1, 10 ** 5 + 1):
	a[i] = palindrome(i)
	a_sum[i] = a_sum[i - 1] + a[i]

def solve():
	(l, r) = IN()
	result = 1
	power = a_sum[r] - a_sum[l]
	base = a[l]
	while power:
		if power % 2 == 0:
			base = base % (10 ** 9 + 7) * (base % (10 ** 9 + 7)) % (10 ** 9 + 7)
			power //= 2
		else:
			result = result % (10 ** 9 + 7) * (base % (10 ** 9 + 7)) % (10 ** 9 + 7)
			power -= 1
	print(result)

def main():
	t = 1
	t = I()
	for i in range(1, t + 1):
		solve()
main()


chfr = [0] * 100001
pch = [0] * 100001
for i in range(1, 100001):
	temp = i // 10
	if temp != 0:
		temp = str(temp)
		temp = temp[::-1]
		chfr[i] = int(str(i) + temp)
	else:
		chfr[i] = i
	pch[i] = chfr[i] + pch[i - 1]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	y = pch[r] - pch[l]
	x = chfr[l]
	ans = int(pow(x, y, 1000000007))
	print(ans)


try:

	class Pl:

		def __init__(self, n):
			self.n = n
			self.i = 0
			self.pl = [0] * n
			self.pre = [0] * n

		def add(self, v):
			self.pl[self.i] = v
			self.pre[self.i] = v
			if self.i != 0:
				self.pre[self.i] += self.pre[self.i - 1]
			self.i = self.i + 1

		def fill(self):
			return self.i == self.n

		def rangedpre(self, l, r):
			return self.pre[r] - self.pre[l]

		def basePl(self, l):
			return self.pl[l]

	def Opl(a):
		n = a
		pal = a
		n = n // 10
		while n > 0:
			pal = pal * 10 + n % 10
			n = n // 10
		return pal

	def makePl(pl):
		i = 1
		while not pl.fill():
			pl.add(Opl(i))
			i += 1

	def cal(l, r, pl):
		power = pl.rangedpre(l - 1, r - 1)
		base = pl.basePl(l - 1)
		return pow(base, power, 1000000007)
	pl = Pl(100001)
	makePl(pl)
	T = int(input())
	while T > 0:
		(l, r) = map(int, input().split())
		print(cal(l, r, pl))
		T -= 1
except:
	pass


class palindrome:

	def __init__(self, n):
		self.n = n
		self.i = 0
		self.palindrome = [0] * n
		self.prefix = [0] * n

	def add(self, v):
		self.palindrome[self.i] = v
		self.prefix[self.i] = v
		if self.i != 0:
			self.prefix[self.i] += self.prefix[self.i - 1]
		self.i = self.i + 1

	def fill(self):
		return self.i == self.n

	def rangeprefix(self, l, r):
		return self.prefix[r] - self.prefix[l]

	def basepalindrome(self, l):
		return self.palindrome[l]

def oddpalindrome(a):
	n = a
	pal = a
	n = n // 10
	while n > 0:
		pal = pal * 10 + n % 10
		n = n // 10
	return pal

def makepalindrome(palindrome):
	i = 1
	while not palindrome.fill():
		palindrome.add(oddpalindrome(i))
		i += 1

def cal(l, r, palindrome):
	power = palindrome.rangeprefix(l - 1, r - 1)
	base = palindrome.basepalindrome(l - 1)
	return pow(base, power, 1000000007)
palindrome = palindrome(100001)
makepalindrome(palindrome)
t = int(input())
while t > 0:
	(l, r) = map(int, input().split())
	print(cal(l, r, palindrome))
	t -= 1


def binom(al, ar):
	mod = 10 ** 9 + 7
	res = 1
	while ar:
		if ar % 2 != 0:
			res = res * al % mod
		ar = ar // 2
		al = al * al % mod
	return res
q = int(input())
ar = [0] * (10 ** 5 + 1)
arsm = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	temp = i
	n1 = list(map(int, str(i // 10)))
	res = int(''.join(map(str, n1[::-1])))
	if res > 0:
		temp = temp * 10 ** len(n1) + res
	ar[i] = temp
	arsm[i] = arsm[i - 1] + ar[i]
for _ in range(q):
	(l, r) = map(int, input().split())
	sm = arsm[r] - arsm[l]
	z = binom(ar[l], sm)
	print(z)


def ans(base, power):
	m = 10 ** 9 + 7
	res = 1
	while power != 0:
		if power % 2 == 0:
			base = base % m * (base % m) % m
			power = power // 2
		else:
			res = res % m * (base % m) % m
			power = power - 1
	return res

def palin(i):
	temp = i
	i = i // 10
	while i > 0:
		temp = temp * 10 + i % 10
		i = i // 10
	return temp
arr = [0] * (10 ** 5 + 1)
p = [0] * (10 ** 5 + 1)
for i in range(1, len(arr)):
	arr[i] = palin(i)
	p[i] = p[i - 1] + arr[i]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	power = p[k] - p[n]
	print(ans(arr[n], power))


def chefora(n):
	if n <= 9:
		return n
	k = n // 10
	return int(str(n) + str(k)[::-1])
pre_sum = [0]
for i in range(1, 100001):
	pre_sum.append(pre_sum[i - 1] + chefora(i))
mod = 10 ** 9 + 7
test = int(input())

def power(base, poer):
	sol = 1
	while poer > 0:
		if poer % 2 != 0:
			sol = sol % mod * base % mod % mod
			poer -= 1
		else:
			poer = poer // 2
			base = base % mod * (base % mod) % mod
	return sol
ans = []
for _ in range(test):
	x = list(map(int, input().split()))
	l = x[0]
	r = x[1]
	m = pre_sum[r] - pre_sum[l]
	ans.append(power(chefora(l), m))
for i in ans:
	print(i)


def power(a, n):
	res = 1
	p = n
	base = a
	while p > 0:
		if p % 2 == 0:
			p = p // 2
			base = base % (10 ** 9 + 7) * (base % (10 ** 9 + 7)) % (10 ** 9 + 7)
		else:
			p -= 1
			res = res % (10 ** 9 + 7) * (base % (10 ** 9 + 7)) % (10 ** 9 + 7)
	return res

def createChefora(n):
	temp = n
	n = n // 10
	while n > 0:
		temp = temp * 10 + n % 10
		n = n // 10
	return temp
chefora = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	chefora[i] = createChefora(i)
prefixsm = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	prefixsm[i] = prefixsm[i - 1] + chefora[i]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	ans = power(chefora[l], prefixsm[r] - prefixsm[l])
	print(ans)


class Pre:

	def __init__(self, n):
		self.n = n
		self.i = 0
		self.palindromes = [0] * n
		self.prefixSums = [0] * n

	def add(self, val):
		self.palindromes[self.i] = val
		self.prefixSums[self.i] = val
		if self.i != 0:
			self.prefixSums[self.i] += self.prefixSums[self.i - 1]
		self.i = self.i + 1

	def isFull(self):
		return self.i == self.n

	def getPrefixSumInRange(self, L, R):
		return self.prefixSums[R] - self.prefixSums[L]

	def getFirstPalin(self, index):
		return self.palindromes[index]

def odd(inp):
	n = inp
	palin = inp
	n = n // 10
	while n > 0:
		palin = palin * 10 + n % 10
		n = n // 10
	return palin

def gen(pre):
	i = 1
	while not pre.isFull():
		pre.add(odd(i))
		i = i + 1

def solve(L, R, pre):
	power = pre.getPrefixSumInRange(L - 1, R - 1)
	base = pre.getFirstPalin(L - 1)
	return pow(base, power, 1000000007)
pre = Pre(100001)
gen(pre)
q = int(input())
while q > 0:
	q = q - 1
	line = input().split(' ')
	(L, R) = (int(line[0]), int(line[1]))
	print(solve(L, R, pre))


def fp(base, power):
	mod = 10 ** 9 + 7
	res = 1
	while power != 0:
		if power % 2 == 0:
			base = base % mod * (base % mod) % mod
			power = power // 2
		else:
			res = res % mod * (base % mod) % mod
			power = power - 1
	return res

def fsf(num):
	pa = num
	num = num // 10
	while num > 0:
		pa = pa * 10 + num % 10
		num = num // 10
	return pa
arr = [0] * (10 ** 5 + 1)
ar = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	arr[i] = fsf(i)
	ar[i] = ar[i - 1] + arr[i]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	power = ar[r] - ar[l]
	print(fp(arr[l], power))


def oddPalindrome(val):
	(n, pal) = (val, val)
	n //= 10
	while n > 0:
		pal = pal * 10 + n % 10
		n //= 10
	return pal

class Palindrome:

	def __init__(self, n):
		super(Palindrome, self).__init__()
		self.n = n
		self.i = 0
		self.palin = [0] * n
		self.pre = [0] * n

	def fill(self):
		return self.i == self.n

	def add(self, v):
		self.palin[self.i] = v
		self.pre[self.i] = v
		if self.i != 0:
			self.pre[self.i] += self.pre[self.i - 1]
		self.i = self.i + 1

	def basePalindrome(self, l):
		return self.palin[l]

	def rangedPrefix(self, l, r):
		return self.pre[r] - self.pre[l]

def create(palin):
	idx = 1
	while not palin.fill():
		palin.add(oddPalindrome(idx))
		idx += 1

def cal(l, r, palin):
	power = palin.rangedPrefix(l - 1, r - 1)
	base = palin.basePalindrome(l - 1)
	return pow(base, power, 1000000007)

class Solution(object):
	try:
		obj = Palindrome(100001)
		create(obj)
		q = int(input())
		while q > 0:
			(l, r) = map(int, input().split())
			print(cal(l, r, obj))
			q -= 1
	except Exception as e:
		raise e


def power(bs, pw):
	mod = 10 ** 9 + 7
	if pw == 0:
		return 1
	elif pw == 1:
		return bs
	if pw & 1:
		res = bs % mod * power(bs, pw - 1) % mod % mod
	else:
		res = power(bs, pw // 2) % mod
		res *= res
		res %= mod
	return res
chefola_no = [0]
presums = [0]
for i in range(1, 10 ** 5 + 1):
	s = str(i)
	num = int(s[:-1] + s[::-1])
	chefola_no.append(num)
	presums.append(presums[i - 1] + num)
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	pwr = presums[r] - presums[l]
	print(power(chefola_no[l], pwr))


def power(b, p):
	mod = 10 ** 9 + 7
	ans = 1
	while p != 0:
		if p % 2 == 0:
			b = b % mod * (b % mod) % mod
			p = p // 2
		else:
			ans = ans % mod * (b % mod) % mod
			p = p - 1
	return ans

def find(n):
	k = n
	n = n // 10
	while n > 0:
		k = k * 10 + n % 10
		n = n // 10
	return k
a = [0] * (10 ** 5 + 1)
s = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	a[i] = find(i)
	s[i] = s[i - 1] + a[i]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	p = s[r] - s[l]
	print(power(a[l], p))


def convert(i):
	n = i // 10
	while n != 0:
		i = i * 10 + n % 10
		n = n // 10
	return i
arr = [0] * 100005
pre = [0] * 100005
for i in range(1, len(arr)):
	arr[i] = convert(i)
	pre[i] = arr[i] + pre[i - 1]
m = 10 ** 9 + 7
for t in range(int(input())):
	(l, r) = list(map(int, input().split()))
	a = arr[l]
	p = pre[r] - pre[l]
	res = 1
	while p > 0:
		if p % 2 == 0:
			a = a % m * (a % m) % m
			p //= 2
		else:
			p -= 1
			res = res % m * (a % m) % m
	print(res % m)