Natasha, Sasha and the Prefix Sums

题意翻译

## 题目描述 NaCly_Fish 最喜欢的数字是 $n$ 和 $1$；$\mathsf E \color{red} \mathsf{ntropyIncreaser}$ 最喜欢 $m$ 和 $-1$。 有一天，她们在一起写出了一个长度为 $n+m$，有 $n$ 个 $1$ 和 $m$ 个 $-1$ 的序列 $a$，定义其最大前缀和为： $$\large \max\{ 0,\max\limits_{1\le i\le n+m}\sum\limits_{j=1}^ia_j \}$$ 换句话说，就是对于 $a$ 的前缀和的所有项和 $0$ 取 $\max$ 的值。 NaCly_Fish 想知道，对于全部可能的序列，它们的 最大前缀和 之和是多少。 为了防止答案过大，要对 ${998244\textcolor{red}853}$ (是个质数) 取模。 $\mathsf E \color{red} \mathsf{ntropyIncreaser}$ 只用 1s 就想到了做法，但是 NaCly_Fish 还不会，你能帮帮她吗？ ## 输入格式 一行两个非负整数 $n,m$ ## 输出格式 一行一个整数表示答案。 ## 说明 【样例 $3$ 解释】 可能的序列有 $6$ 种： $1,1,-1,-1$ $1,-1,1,-1$ $1,-1,-1,1$ $-1,1,1,-1$ $-1,1,-1,1$ $-1,-1,1,1$ 它们的最大前缀和分别为 $2,1,1,1,0,0$，加起来答案为 $5$。 【数据范围】 $0\le n,m \le 2000$

题目描述

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 ) $ $ </p><p>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$.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

0 2

输出样例 #1

0

输入样例 #2

2 0

输出样例 #2

2

输入样例 #3

2 2

输出样例 #3

5

输入样例 #4

2000 2000

输出样例 #4

674532367

说明

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 $ .