When you look at photographs of watches and clocks, you'll find that they almost always show the time 10:10. There are lots of theories and even urban legends about this. For example, when showing 10:10, the hands look like a smile, and so you are more inclined to buy the watch or clock :D (a form of subliminal advertising).

Now, you are given $N$ and ${M}$. You are to find the number of sequences $A_{1},A_{2},\ldots,A_{N}$ such that:

${A_1}$ is a number of the form ${1010}^K$ for some $1\leq K\leq M$,
If $P=A_2\cdot A_3\cdots A_N$, then ${A_1}$ is divisible by ${P}$, and $\mbox{P}$ is divisible by ${1010}$, and
$A_2,A_3,\ldots,A_N$ are squarefree.

Since the number can be very large, only give the number modulo ${2000003}$.

Input Format 

The first line of input contains a single integer ${T}$, which is the number of test cases. The following lines contain the test cases.

Each test case consists of one line containing two integers, $N$ and ${M}$.

Constraints 

$1\leq T\leq10^5$ 

$2\leq N\leq M\leq10^{12}$  

Output Format 

For each test case, output a single line containing the answer.

Sample Input  

2
2 3
3 3

Sample Output  

3
62

Explanation 

For the first test case, the possible sequences are: 

$\{1010,1010\}$, 

$\{1020100,1010\}$, 

${103031000},{1010}$

Difficulty: HARD
Tags: Number theory

Starter code:

Solutions:
import sys

def read_one():
	return sys.stdin.readline().strip()

def read_spaced():
	return sys.stdin.readline().strip().split()

def read_spaced_int():
	return map(int, read_spaced())
mod = 2 * 10 ** 6 + 3
N_max = mod - 1
fac = [1] * (N_max + 1)
invfac = [1] * (N_max + 1)
inv2 = pow(2, mod - 2, mod)
for i in range(2, N_max + 1):
	fac[i] = fac[i - 1] * i % mod
invfac[N_max] = pow(fac[N_max], mod - 2, mod)
for i in reversed(range(2, N_max)):
	invfac[i] = invfac[i + 1] * (i + 1) % mod

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * invfac[k] * invfac[n - k] % mod

def get_digits(N, B):
	D = []
	while N:
		(N, d) = divmod(N, B)
		D.append(d)
	return D

def catalan(N):
	(D1, D2) = (get_digits(N, mod), get_digits(2 * N, mod))
	ans = 1
	for i in range(len(D1)):
		if D1[i] > D2[i]:
			return 0
		ans = ans * binomial(D2[i], D1[i]) % mod
	return ans

def S1(N):
	return (N + 2) * pow(2, N - 1, mod) % mod

def S2(N):
	return ((N + 2) * pow(2, 2 * N - 1, mod) - inv2 * N * catalan(N)) % mod

def S3(N):
	if N == 1:
		return 9
	c = catalan(N)
	return ((N + 2) * pow(2, 3 * N - 1, mod) - 3 * N * c * pow(2, N - 2, mod)) % mod

def solve(N, M):
	ans = (M - N) * pow(pow(2, N, mod) - 1, 3, mod) % mod
	ans = (ans + S3(N) - 3 * S2(N) + 3 * S1(N) - N - 1) % mod
	return ans
T = int(read_one())
for _ in range(T):
	(N, M) = read_spaced_int()
	print(solve(N - 1, M))


import sys

def read_one():
	return sys.stdin.readline().strip()

def read_spaced():
	return sys.stdin.readline().strip().split()

def read_spaced_int():
	return map(int, read_spaced())
mod = 2 * 10 ** 6 + 3
N_max = mod - 1
fac = [1] * (N_max + 1)
invfac = [1] * (N_max + 1)
inv2 = pow(2, mod - 2, mod)
for i in range(2, N_max + 1):
	fac[i] = fac[i - 1] * i % mod
invfac[N_max] = pow(fac[N_max], mod - 2, mod)
for i in reversed(range(2, N_max)):
	invfac[i] = invfac[i + 1] * (i + 1) % mod

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * invfac[k] * invfac[n - k] % mod

def get_digits(N, B):
	D = []
	while N:
		(N, d) = divmod(N, B)
		D.append(d)
	return D

def catalan(N):
	(D1, D2) = (get_digits(N, mod), get_digits(2 * N, mod))
	ans = 1
	for i in range(len(D1)):
		if D1[i] > D2[i]:
			return 0
		ans = ans * binomial(D2[i], D1[i]) % mod
	return ans

def S1(N):
	return (N + 2) * pow(2, N - 1, mod) % mod

def S2(N):
	return ((N + 2) * pow(2, 2 * N - 1, mod) - inv2 * N * catalan(N)) % mod

def S3(N):
	if N == 1:
		return 9
	c = catalan(N)
	return ((N + 2) * pow(2, 3 * N - 1, mod) - 3 * N * c * pow(2, N - 2, mod)) % mod

def solve(N, M):
	ans = (M - N) * pow(pow(2, N, mod) - 1, 3, mod) % mod
	ans = (ans + S3(N) - 3 * S2(N) + 3 * S1(N) - N - 1) % mod
	return ans
T = int(read_one())
for _ in range(T):
	(N, M) = read_spaced_int()
	print(solve(N - 1, M))


mod = 2000003
factlist = [1]
factinvlist = [mod - 1] * mod
for i in range(1, mod):
	factlist.append(factlist[-1] * i % mod)
	factinvlist[mod - i - 1] = factlist[i] if i % 2 == 0 else mod - factlist[i]

def choose(n, r):
	toret = 1
	currn = n
	currr = r
	while currn > 0:
		if currr % mod > currn % mod:
			return 0
		else:
			toret = toret * factlist[currn % mod] * factinvlist[currr % mod] * factinvlist[(currn - currr) % mod] % mod
		currn //= mod
		currr //= mod
	return toret
t = int(input())
for _ in range(t):
	[n, m] = list(map(int, input().split(' ')))
	toret = ((n + 1) * pow(2, 3 * n - 4, mod) - 3 * pow(2, n - 3, mod) * (n - 1) * choose(2 * (n - 1), n - 1)) % mod if n > 2 else 9
	toret = (toret - 3 * ((n + 1) * pow(2, 2 * n - 3, mod) - (n - 1) * choose(2 * (n - 1), n - 1) * pow(2, mod - 2, mod))) % mod
	toret += 3 * (n + 1) * pow(2, n - 2, mod) - n
	currnsum = pow(2, n - 1, mod) - 1
	toret = (toret + (m - n + 1) * currnsum * currnsum * currnsum) % mod
	print(toret)


import sys

def read_one():
	return sys.stdin.readline().strip()

def read_spaced():
	return sys.stdin.readline().strip().split()

def read_spaced_int():
	return map(int, read_spaced())
mod = 2 * 10 ** 6 + 3
N_max = mod - 1
fac = [1] * (N_max + 1)
invfac = [1] * (N_max + 1)
inv2 = pow(2, mod - 2, mod)
for i in range(2, N_max + 1):
	fac[i] = fac[i - 1] * i % mod
invfac[N_max] = pow(fac[N_max], mod - 2, mod)
for i in reversed(range(2, N_max)):
	invfac[i] = invfac[i + 1] * (i + 1) % mod

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * invfac[k] * invfac[n - k] % mod

def get_digits(N, B):
	D = []
	while N:
		(N, d) = divmod(N, B)
		D.append(d)
	return D

def catalan(N):
	(D1, D2) = (get_digits(N, mod), get_digits(2 * N, mod))
	ans = 1
	for i in range(len(D1)):
		if D1[i] > D2[i]:
			return 0
		ans = ans * binomial(D2[i], D1[i]) % mod
	return ans

def S1(N):
	return (N + 2) * pow(2, N - 1, mod) % mod

def S2(N):
	return ((N + 2) * pow(2, 2 * N - 1, mod) - inv2 * N * catalan(N)) % mod

def S3(N):
	if N == 1:
		return 9
	c = catalan(N)
	return ((N + 2) * pow(2, 3 * N - 1, mod) - 3 * N * c * pow(2, N - 2, mod)) % mod

def solve(N, M):
	ans = (M - N) * pow(pow(2, N, mod) - 1, 3, mod) % mod
	ans = (ans + S3(N) - 3 * S2(N) + 3 * S1(N) - N - 1) % mod
	return ans
T = int(read_one())
for _ in range(T):
	(N, M) = read_spaced_int()
	print(solve(N - 1, M))


p = 2000003

def modp_pow(x, n):
	n = n % (p - 1)
	x = x % p
	if x == 0:
		return 0
	result = 1
	while n > 0:
		if n % 2 == 1:
			result = x * result % p
		x = x * x % p
		n = n // 2
	return result

def x10(x):
	x2 = x * x % p
	x4 = x2 * x2 % p
	x8 = x4 * x4 % p
	return x8 * x2 % p

def modp_inv(x):
	y = x * x % p
	for i in range(6):
		y = x10(y)
	return y * x % p

def modp_sqinv(x):
	for i in range(6):
		x = x10(x)
	return x % p

class fac_mod_p:

	def __init__(self, p):
		self.p = p
		self.value = 1

	def __call__(self, x):
		self.value = self.value * x % self.p
		return self.value
f = fac_mod_p(p)
mod_p_fac = [f(i) for i in range(1, p)]

def binom(k):
	if k > p / 2:
		return 0
	if k < 1:
		return 1
	kfac = mod_p_fac[k - 1]
	return mod_p_fac[2 * k - 1] * modp_sqinv(kfac * kfac % p) % p

def modp_binom(k):
	(k1, k2) = (k // p, k % p)
	return binom(k1) * binom(k2) % p

def answer(N, M):
	n = N - 1
	n_modp = n % p
	two_to_n_1 = modp_pow(2, n - 1)
	two_to_n = 2 * two_to_n_1 % p
	two_to_n_1_to_3 = (two_to_n - 1) * (two_to_n - 1) % p * (two_to_n - 1)
	first_term = (M + 1) % p * (two_to_n_1_to_3 % p)
	second_term = two_to_n_1 * n_modp % p * ((two_to_n * (two_to_n - 3) + 3) % p)
	third_term = 3 * (2 * n_modp - 1) * (two_to_n_1 - 1) % p * modp_binom(n - 1)
	return (first_term - second_term - third_term) % p
T = int(input())
test_cases = [tuple(map(int, input().split())) for _ in range(T)]
results = [answer(N, M) for (N, M) in test_cases]
print(*results, sep='\n')