Codeforces Round 581 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

number theory

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Natasha, Sasha and the Prefix Sums

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputNatasha'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$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/01/2023 18:48:38 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|