Read problems statements in Mandarin Chinese  and Russian. 

Given three positive integers N, L and R, find the number of non-decreasing sequences of size at least 1 and at most N, such that each element of the sequence lies between L and R, both inclusive.

Print the answer modulo 10^{6}+3.

------ Input ------ 

First line of input contains T, the number of the test cases.
Each of next T lines contains three space separated integers N, L and R.

------ Output ------ 

For each test case print the answer modulo 10^{6}+3 in a single line.

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

$1 ≤ T ≤ 100$
$L ≤ R$

------ Subtasks ------ 

$Subtask #1 (20 points): 1 ≤ N, L, R ≤ 100
$$Subtask #2 (30 points): 1 ≤ N, L, R ≤ 10^{4}
$$Subtask #3 (50 points): 1 ≤ N, L, R ≤ 10^{9}

----- Sample Input 1 ------ 
2
1 4 5
2 4 5
----- Sample Output 1 ------ 
2
5
----- explanation 1 ------ 
test #1: [4] and [5] are the two sequences.
test #2: [4], [5], [4, 4], [4, 5] and [5, 5] are the five sequences.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
cl = [1]

def factorial2(n, mod):
	if n > len(cl):
		for i in range(len(cl), n):
			cl.append((i + 1) * cl[i - 1] % mod)
	return cl[n - 1]

def select7(n, k, mod):
	if n > mod or k > mod:
		(n1, k1) = (n // mod, k // mod)
		(n0, k0) = (n % mod, k % mod)
		if n1 < k1 or n0 < k0:
			return 0
		return select7(n1, k1, mod) * select7(n0, k0, mod)
	if n == k or k == 0:
		return 1
	a = factorial2(n, mod)
	b = factorial2(k, mod)
	b = pow(b, mod - 2, mod)
	c = factorial2(n - k, mod)
	c = pow(c, mod - 2, mod)
	return a * b * c % mod

def solve2(n, m, p):
	return (select7(m + n, n, p) - 1) % p
for t in range(int(input())):
	(n, l, r) = [int(x) for x in input().split()]
	print(solve2(n, r - l + 1, 10 ** 6 + 3))


import math
silniaTab = [1]
R = 1000003

def pot(a, n):
	if n == 0:
		return 1
	if n == 1:
		return a
	t = pot(a, n // 2)
	t *= t
	if n % 2 == 1:
		t *= a
	return t % R

def odwr(a):
	return pot(a % R, R - 2)

def silnia(a):
	tmp = silniaTab[a % R] * pot(silniaTab[R - 1], a // R) % R
	for i in range(1, a // R + 1):
		tmp *= i
		tmp %= R
	return tmp
for i in range(1, R + 2):
	silniaTab.append(silniaTab[-1] * i % R)
T = int(input())
for t in range(T):
	(n, l, r) = map(int, input().split())
	l = r - l + 1
	if (n + l) // R > n // R + l // R:
		print(R - 1)
	else:
		print((silnia(n + l) * odwr(silnia(n) * silnia(l)) + R - 1) % R)


mod = 10 ** 6 + 3

def fact(x):
	if x < len(F):
		return F[x]
	return 0

def nCr(x, y):
	if y > x:
		return 0
	y = min(y, x - y)
	cntX = 0
	p = mod
	while x >= p:
		cntX += x // p
		p *= mod
	cntY = 0
	p = mod
	while y >= p:
		cntY += y // p
		p *= mod
	p = mod
	while x - y >= p:
		cntY += (x - y) // p
		p *= mod
	if cntY == 0 or cntY < cntX:
		return fact(x) * pow(fact(y) * fact(x - y) % mod, mod - 2, mod) % mod
	X = []
	Y = []
	p = mod
	while p <= x:
		p *= mod
	p //= mod
	while p >= 1:
		X.append(x // p)
		x %= p
		p //= mod
	p = mod
	while p <= y:
		p *= mod
	p //= mod
	while p >= 1:
		Y.append(y // p)
		y %= p
		p //= mod
	while len(X) < len(Y):
		X = [0] + X
	while len(Y) < len(X):
		Y = [0] + Y
	ans = 1
	for i in range(len(X)):
		ans *= nCr(X[i], Y[i])
		ans %= mod
	return ans
F = [1]
for i in range(1, 1000010):
	F.append(F[i - 1] * i % mod)
t = int(input())
while t > 0:
	(n, L, R) = map(int, input().split())
	x = R - L
	print((nCr(x + n + 1, n) - 1 + mod) % mod)
	t -= 1


def main():
	MOD = 1000003
	fact = [1]
	for i in range(1, MOD):
		fact.append(fact[i - 1] * i % MOD)

	def small_nCr(ni, mi):
		return fact[ni] * (pow(fact[mi], MOD - 2, MOD) * pow(fact[ni - mi], MOD - 2, MOD) % MOD)

	def Lucas(n, m):
		if n == 0 and m == 0:
			return 1
		ni = n % MOD
		mi = m % MOD
		if mi > ni:
			return 0
		return Lucas(n // MOD, m // MOD) * small_nCr(ni, mi) % MOD
	for T in range(int(input())):
		(N, L, R) = map(int, input().split())
		R -= L - 1
		L = 1
		ans = Lucas(R + N, N)
		print((ans + MOD - 1) % MOD)
main()


p = 10 ** 6 + 3
fact = [1] * p
factinv = [1] * p
for i in range(1, p):
	fact[i] = fact[i - 1] * i % p
	factinv[i] = pow(fact[i], -1, p)
for case in range(int(input())):
	(n, l, r) = [int(x) for x in input().split()]
	a = n + r - l + 1
	u = 1
	while n > 0:
		(i, j) = (a % p, n % p)
		if i >= j:
			u = u * fact[i] * factinv[j] * factinv[i - j] % p
		else:
			u = p
			break
		a //= p
		n //= p
	print(u - 1)


def gcd(a, b):
	while True:
		if a == 0:
			return b
		else:
			b %= a
		if b == 0:
			return a
		else:
			a %= b

def pulverize(a, b):
	apair = (1, 0)
	bpair = (0, 1)
	while True:
		if a == 0:
			return (b, bpair)
		else:
			quot = b // a
			b %= a
			bpair = (bpair[0] - apair[0] * quot, bpair[1] - apair[1] * quot)
		if b == 0:
			return (a, apair)
		else:
			quot = a // b
			a %= b
			apair = (apair[0] - bpair[0] * quot, apair[1] - bpair[1] * quot)

def inverse(a, m):
	a %= m
	(g, (x, n)) = pulverize(a, m)
	n = -n
	if g != 1:
		return None
	elif x < 0:
		factor = -x // m
		if -x % m != 0:
			factor += 1
		x += m * factor
		n += a * factor
	return x
mbase = 1000003
fact = [1]
for i in range(1, 1000003):
	fact.append(fact[i - 1] * i % mbase)

def mod_combi(n, r):
	if r < 0 or r > n:
		return 0
	if r > n - r:
		r = n - r
	prod = 1
	for i in range(r):
		prod *= n - i
		prod %= mbase
	prod *= inverse(fact[r], mbase)
	return prod % mbase

def main():
	t = int(input())
	for it in range(t):
		(n, l, r) = [int(word) for word in input().split()]
		up = n + r - l + 1
		down = n
		res1 = mod_combi(up % mbase, down % mbase)
		res2 = mod_combi(up // mbase, down // mbase)
		res = (res1 * res2 - 1) % mbase
		print(res)
main()