Natasha's favourite numbers are $n$ and $1$, and Sasha's favourite numbers are $m$ and $-1$. One day Natasha and Sasha met and wrote down every possible array of length $n+m$ such that some $n$ of its elements are equal to $1$ and another $m$ elements are equal to $-1$. For each such array they counted its maximal prefix sum, probably an empty one which is equal to $0$ (in another words, if every nonempty prefix sum is less to zero, then it is considered equal to zero). Formally, denote as $f(a)$ the maximal prefix sum of an array $a_{1, \ldots ,l}$ of length $l \geq 0$. Then: 

$$f(a) = \max (0, \smash{\displaystyle\max_{1 \leq i \leq l}} \sum_{j=1}^{i} a_j )$$

Now they want to count the sum of maximal prefix sums for each such an array and they are asking you to help. As this sum can be very large, output it modulo $998\: 244\: 853$.


-----Input-----

The only line contains two integers $n$ and $m$ ($0 \le n,m \le 2\,000$).


-----Output-----

Output the answer to the problem modulo $998\: 244\: 853$.


-----Examples-----
Input
0 2

Output
0

Input
2 0

Output
2

Input
2 2

Output
5

Input
2000 2000

Output
674532367



-----Note-----

In the first example the only possible array is [-1,-1], its maximal prefix sum is equal to $0$. 

In the second example the only possible array is [1,1], its maximal prefix sum is equal to $2$. 

There are $6$ possible arrays in the third example:

[1,1,-1,-1], f([1,1,-1,-1]) = 2

[1,-1,1,-1], f([1,-1,1,-1]) = 1

[1,-1,-1,1], f([1,-1,-1,1]) = 1

[-1,1,1,-1], f([-1,1,1,-1]) = 1

[-1,1,-1,1], f([-1,1,-1,1]) = 0

[-1,-1,1,1], f([-1,-1,1,1]) = 0

So the answer for the third example is $2+1+1+1+0+0 = 5$.

Difficulty: HARD
Tags: Number theory

Combinatorics

Dynamic programming

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
P = 998244853
N = 4000
(f, fi) = ([0] * (N + 1), [0] * (N + 1))
f[0] = 1
for i in range(N):
	f[i + 1] = f[i] * (i + 1) % P
fi[-1] = pow(f[-1], P - 2, P)
for i in reversed(range(N)):
	fi[i] = fi[i + 1] * (i + 1) % P

def C(n, r):
	c = 1
	while n or r:
		(a, b) = (n % P, r % P)
		if a < b:
			return 0
		c = c * f[a] % P * fi[b] % P * fi[a - b] % P
		n //= P
		r //= P
	return c
(n, m) = map(int, input().split())
k = max(n - m - 1, 0)
print((k * C(n + m, m) + sum((C(n + m, m + i) for i in range(k + 1, n))) + 1) % P if n else 0)


(P, N) = (998244853, 4000)
(f, fi) = ([0] * (N + 1), [0] * (N + 1))
(f[0], fi[-1]) = (1, 338887798)
for i in range(N):
	f[i + 1] = f[i] * (i + 1) % P
	fi[N - i - 1] = fi[N - i] * (N - i) % P
C = lambda n, r: f[n] * fi[r] % P * fi[n - r] % P
(n, m) = list(map(int, input().split()))
k = max(n - m - 1, 0)
print((k * C(n + m, m) + sum((C(n + m, m + i) for i in range(k + 1, n))) + 1) % P if n else 0)


mod = 998244853
MAX = 4000
(n, m) = map(int, input().split())
k = [[0 for _ in range(0, m + 1)] for _ in range(0, n + 1)]
l = [[0 for _ in range(0, m + 1)] for _ in range(0, n + 1)]
ans = [[0 for _ in range(0, m + 1)] for _ in range(0, n + 1)]
for x in range(n + 1):
	for y in range(m + 1):
		if x == 0 or y == 0:
			l[x][y] = 1
		else:
			l[x][y] = (l[x - 1][y] + l[x][y - 1]) % mod
for x in range(n + 1):
	for y in range(m + 1):
		if x == 0:
			k[0][y] = 1
		elif x <= y:
			k[x][y] = (k[x - 1][y] + k[x][y - 1]) % mod
for x in range(n + 1):
	for y in range(m + 1):
		if y == 0:
			ans[x][0] = x
		elif x == 0:
			ans[0][y] = 0
		else:
			ans[x][y] = (ans[x - 1][y] + ans[x][y - 1] + k[x][y - 1] + l[x - 1][y] - l[x][y - 1]) % mod
print(int(ans[n][m]))


P = 998244853
(N, M) = list(map(int, input().split()))
fa = [1]
for i in range(4040):
	fa.append(fa[-1] * (i + 1) % P)
fainv = [pow(fa[-1], P - 2, P)]
for i in range(4040)[::-1]:
	fainv.append(fainv[-1] * (i + 1) % P)
fainv = fainv[::-1]

def C(a, b):
	return fa[a] * fainv[a - b] * fainv[b] % P

def calc(i):
	return C(N + M, M) if N - M > i else C(N + M, M + i)
X = [0] * N + [1]
for i in range(N):
	X[i] = calc(i) - calc(i + 1)
print(sum([i * X[i] for i in range(1, N + 1)]) % P)


MOD = 998244853
MAXN = 4000
(fact, inv_fact) = ([0] * (MAXN + 1), [0] * (MAXN + 1))
fact[0] = 1
for i in range(MAXN):
	fact[i + 1] = fact[i] * (i + 1) % MOD
inv_fact[-1] = pow(fact[-1], MOD - 2, MOD)
for i in reversed(range(MAXN)):
	inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def nCr_mod(n, r):
	res = 1
	while n or r:
		(a, b) = (n % MOD, r % MOD)
		if a < b:
			return 0
		res = res * fact[a] % MOD * inv_fact[b] % MOD * inv_fact[a - b] % MOD
		n //= MOD
		r //= MOD
	return res
(n, m) = map(int, input().split())
k = max(n - m - 1, 0)
print((k * nCr_mod(n + m, m) + sum((nCr_mod(n + m, m + i) for i in range(k + 1, n))) + min(1, n)) % MOD)


mod = 998244853

def frac(limit):
	frac = [1] * limit
	for i in range(2, limit):
		frac[i] = i * frac[i - 1] % mod
	fraci = [None] * limit
	fraci[-1] = pow(frac[-1], mod - 2, mod)
	for i in range(-2, -limit - 1, -1):
		fraci[i] = fraci[i + 1] * (limit + i + 1) % mod
	return (frac, fraci)
(frac, fraci) = frac(13413)

def comb(a, b):
	if not a >= b >= 0:
		return 0
	return frac[a] * fraci[b] * fraci[a - b] % mod
(N, M) = list(map(int, input().split()))
print(sum((comb(N + M, min(i, M)) for i in range(N))) % mod)


(n, m) = list(map(int, input().split()))
mod = 998244853
fact = [1]
invfact = [1]

def pw(x, y):
	ans = 1
	while y:
		if y & 1:
			ans = ans * x % mod
		x = x * x % mod
		y >>= 1
	return ans

def inv(x):
	return pw(x, mod - 2)
for i in range(1, n + m + 1):
	fact.append(fact[i - 1] * i % mod)
	invfact.append(invfact[i - 1] * inv(i) % mod)
mn = max(0, n - m)

def ways_to(sub):
	inc = (n + m + sub) // 2
	return fact[n + m] * invfact[inc] * invfact[n + m - inc] % mod
ans = 0
ways = [0 for x in range(0, n + 2)]
for i in range(mn, n + 1):
	ways[i] = ways_to(n - m) - ways_to(2 * i - n + m)
ways[n + 1] = ways_to(n - m)
for i in range(1, n + 1):
	ans += i * (ways[i + 1] - ways[i])
	ans %= mod
if ans < 0:
	ans += mod
print(ans)


import sys
import math
MOD = 998244853

def prepare_c(n):
	result = [1]
	last = [1, 1]
	for i in range(2, n + 1):
		new = [1]
		for j in range(1, i):
			new.append((last[j - 1] + last[j]) % MOD)
		new.append(1)
		last = new
	return new

def main():
	(a, b) = tuple([int(x) for x in input().split()])
	if a + b == 0:
		print(0)
		return
	c = prepare_c(a + b)
	min_lv = max(0, a - b)
	max_lv = a
	res = 0
	res += min_lv * c[a] % MOD
	for lv in range(min_lv + 1, max_lv + 1):
		t = 2 * lv - a + b
		res += c[(a + b + t) // 2]
		res = res % MOD
	print(res)
main()


MOD = 998244853
N = 4000
fact = [1] * (N + 1)
invfact = [1] * (N + 1)
for i in range(1, N + 1):
	fact[i] = fact[i - 1] * i % MOD
invfact[N] = pow(fact[N], MOD - 2, MOD)
for i in range(N - 1, 0, -1):
	invfact[i] = invfact[i + 1] * (i + 1) % MOD

def C(n, k):
	return fact[n] * invfact[k] * invfact[n - k] % MOD if n >= k else 0

def main():
	(n, m) = [int(x) for x in input().split()]
	ans = 0
	for i in range(1, n + 1):
		if n - i >= m:
			ans += C(n + m, n)
		else:
			ans += C(n + m, m + i)
		if ans >= MOD:
			ans -= MOD
	print(ans)
main()


import sys
(n, m) = list(map(int, sys.stdin.readline().strip().split()))
p = 998244853
G = [[0 for i in range(0, m + 1)] for j in range(0, n + 1)]
H = [[0 for i in range(0, m + 1)] for j in range(0, n + 1)]
B = [[0 for i in range(0, m + 1)] for j in range(0, n + 1)]
for i in range(0, n + 1):
	for j in range(0, m + 1):
		if i == 0 or j == 0:
			B[i][j] = 1
		else:
			B[i][j] = (B[i - 1][j] + B[i][j - 1]) % p
for i in range(0, n + 1):
	for j in range(0, m + 1):
		if i == 0:
			H[i][j] = 1
		elif j >= i:
			H[i][j] = (H[i - 1][j] + H[i][j - 1]) % p
for i in range(0, n + 1):
	for j in range(0, m + 1):
		if j == 0:
			G[i][0] = i
		elif i == 0:
			G[0][j] = 0
		else:
			G[i][j] = (G[i - 1][j] + G[i][j - 1] + H[i][j - 1] + B[i - 1][j] - B[i][j - 1]) % p
print(G[n][m])


(n, m) = map(int, input().split())
mod = 998244853
inv = [0] * 5000
fac = [0] * 5000
invfac = [0] * 5000
invfac[0] = invfac[1] = 1
fac[0] = fac[1] = 1
inv[0] = inv[1] = 1
for i in range(2, 4500):
	inv[i] = (mod - mod // i) * inv[mod % i] % mod
for i in range(2, 4500):
	fac[i] = i * fac[i - 1] % mod
	invfac[i] = inv[i] * invfac[i - 1] % mod

def c(x, y):
	if x < y:
		return 0
	return fac[x] * invfac[x - y] % mod * invfac[y] % mod

def cal(x, y):
	if x > y:
		return 0
	return c(x + y, y) - c(x + y, y + 1)
pre = [0] * 2005
now = [0] * 2005
for i in range(1, n + 1):
	now[0] = i
	for k in range(1, m + 1):
		pre[k] = now[k]
	for j in range(1, m + 1):
		now[j] = pre[j] + c(i + j - 1, j) + now[j - 1] - c(i + j - 1, i) + cal(i, j - 1)
		now[j] %= mod
print(now[m])