Heidi the Cow is aghast: cracks in the northern Wall? Zombies gathering outside, forming groups, preparing their assault? This must not happen! Quickly, she fetches her HC^2 (Handbook of Crazy Constructions) and looks for the right chapter:

How to build a wall:  Take a set of bricks.  Select one of the possible wall designs. Computing the number of possible designs is left as an exercise to the reader.  Place bricks on top of each other, according to the chosen design. 

This seems easy enough. But Heidi is a Coding Cow, not a Constructing Cow. Her mind keeps coming back to point 2b. Despite the imminent danger of a zombie onslaught, she wonders just how many possible walls she could build with up to n bricks.

A wall is a set of wall segments as defined in the easy version. How many different walls can be constructed such that the wall consists of at least 1 and at most n bricks? Two walls are different if there exist a column c and a row r such that one wall has a brick in this spot, and the other does not.

Along with n, you will be given C, the width of the wall (as defined in the easy version). Return the number of different walls modulo 10^6 + 3.


-----Input-----

The first line contains two space-separated integers n and C, 1 ≤ n ≤ 500000, 1 ≤ C ≤ 200000.


-----Output-----

Print the number of different walls that Heidi could build, modulo 10^6 + 3.


-----Examples-----
Input
5 1

Output
5

Input
2 2

Output
5

Input
3 2

Output
9

Input
11 5

Output
4367

Input
37 63

Output
230574



-----Note-----

The number 10^6 + 3 is prime.

In the second sample case, the five walls are: 

            B        B

B., .B, BB, B., and .B



In the third sample case, the nine walls are the five as in the second sample case and in addition the following four: 

B    B

B    B  B        B

B., .B, BB, and BB

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Starter code:

Solutions:
(n, c) = list(map(int, input().split()))
mod = 10 ** 6 + 3
inv = [0, 1]
for i in range(2, max(n, c) + 1):
	inv.append(inv[mod % i] * (mod - mod // i) % mod)
ans = 1
for i in range(1, n + c + 1):
	ans = ans * i % mod
for i in range(1, c + 1):
	ans = ans * inv[i] % mod
for i in range(1, n + 1):
	ans = ans * inv[i] % mod
ans += mod - 1
ans %= mod
print(ans)


result = 0
mod = 10 ** 6 + 3
(n, C) = map(int, input().split())

def fact(n):
	fact = 1
	for i in range(1, n + 1):
		fact = fact * i % mod
	return fact

def pow(a, b):
	p = 1
	for i in range(b):
		p = a * p % mod
	return p
result = fact(n + C) * pow(fact(n), mod - 2) * pow(fact(C), mod - 2) - 1
print(int(result % mod))


import math
import operator as op
from functools import reduce
from operator import mul
from fractions import Fraction

def nCk(n, k):
	return int(reduce(mul, (Fraction(n - i, i + 1) for i in range(k)), 1))

def ncr(n, r):
	r = min(r, n - r)
	if r == 0:
		return 1
	numer = reduce(op.mul, range(n, n - r, -1))
	denom = reduce(op.mul, range(1, r + 1))
	return numer // denom

def modPow(a, x, p):
	res = 1
	while x > 0:
		if x % 2 != 0:
			res = res * a % p
		a = a * a % p
		x = int(x / 2)
	return res

def modInverse(a, p):
	return modPow(a, p - 2, p)

def modBinomial(n, k, p):
	numerator = 1
	for i in range(k):
		numerator = numerator * (n - i) % p
	denominator = 1
	for i in range(1, k + 1):
		denominator = denominator * i % p
	return numerator * modInverse(denominator, p) % p
(n, c) = input().split()
n = int(n)
c = int(c)
ans = modBinomial(c + n, c, 1000003) - 1
print(int(ans))


M = pow(10, 6) + 3

def wall(n, c):
	fact = factorial(n + c)
	(_, inv_n, _) = extended_euclidean_alg_1(fact[n], M)
	(_, inv_c, _) = extended_euclidean_alg_1(fact[c], M)
	return (fact[n + c] * (inv_n % M) % M * (inv_c % M) % M - 1) % M

def factorial(m):
	facts = [1 for _ in range(m + 1)]
	for n in range(1, m + 1):
		facts[n] = facts[n - 1] * n % M
	return facts

def extended_euclidean_alg_1(a, b):
	if not b:
		return (0, 1, 0)
	(u0, u1) = (1, 0)
	(v0, v1) = (0, 1)
	while b:
		q = a // b
		r = a - b * q
		u = u0 - q * u1
		v = v0 - q * v1
		a = b
		b = r
		u0 = u1
		u1 = u
		v0 = v1
		v1 = v
	return (a, u0, v0)

def main():
	(n, c) = [int(i) for i in input().split()]
	count = wall(n, c)
	print(int(count))
main()


result = 0
mod = 10 ** 6 + 3
(n, C) = map(int, input().split())

def fact(n):
	fact = 1
	for i in range(1, n + 1):
		fact = fact * i % mod
	return fact

def pow(a, b):
	exp = 1
	x = a % mod
	b = b % (mod - 1)
	while b > 0:
		if b % 2 == 1:
			exp = exp * x % mod
		x = x * x % mod
		b = b // 2
	return exp
result = fact(n + C) * pow(fact(n), mod - 2) * pow(fact(C), mod - 2) - 1
print(int(result % mod))


import math
m = int(1000000.0 + 3)
(a, b) = input().split()
a = int(a)
b = int(b)
A = 1
B = 1
for i in range(2, a + b + 1):
	A = A * i % m
	if i <= a:
		B = B * i % m
	if i <= b:
		B = B * i % m
print((A * pow(B, m - 2, m) - 1) % m)


M = pow(10, 6) + 3

def wall(n, c):
	fact = factorial(n + c)
	inv_n = pow(fact[n], M - 2, M)
	inv_c = pow(fact[c], M - 2, M)
	return (fact[n + c] * (inv_n % M) % M * (inv_c % M) % M - 1) % M

def factorial(m):
	facts = [1 for _ in range(m + 1)]
	for n in range(1, m + 1):
		facts[n] = facts[n - 1] * n % M
	return facts

def main():
	(n, c) = [int(i) for i in input().split()]
	count = wall(n, c)
	print(int(count))
main()


import sys
MOD = 10 ** 6 + 3
fact = [1] * (7 * 10 ** 5 + 10)
for i in range(1, len(fact)):
	fact[i] = fact[i - 1] * i % MOD

def Binom(n, k):
	return fact[n] * (pow(fact[n - k], MOD - 2, MOD) * pow(fact[k], MOD - 2, MOD)) % MOD % MOD

def solution(n, C):
	return Binom(n + C, C) - 1
(n, c) = map(int, input().split())
print(solution(n, c))


def fact(n, mod):
	ans = 1
	for i in range(1, n + 1):
		ans = ans * i % mod
	return ans

def inv1(n, mod):
	ans = 1
	for i in range(mod - 2):
		ans = ans * n % mod
	return ans

def inv2(n, mod):
	return pow(n, mod - 2, mod)
mod = 1000003
(n, c) = [int(i) for i in input().split()]
a = fact(n + c, mod)
b = fact(n, mod)
c = fact(c, mod)
b = inv1(b, mod)
c = inv2(c, mod)
ans = a * b % mod * c % mod
ans -= 1
if ans < 0:
	ans += mod
print(ans)


import sys
with sys.stdin as f:
	(n, C) = f.readline().split(' ')
	(n, C) = (int(n), int(C))
p = 1000003

def compute_mod_fact(n, p):
	res = 1
	for i in range(1, n + 1):
		res = res * i % p
	return res

def compute_mod_mult(n, a, p):
	res = 1
	for _ in range(a):
		res = res * n % p
	return res
res = compute_mod_fact(n + C, p)
res1 = compute_mod_fact(n, p)
res1 = compute_mod_mult(res1, p - 2, p)
res2 = compute_mod_fact(C, p)
res2 = compute_mod_mult(res2, p - 2, p)
res = (res * res1 * res2 - 1) % p
print(res)