← 返回题目列表

Codeforces · 1204/E

E. 娜塔莎、萨莎和前缀和

中文机器翻译题面 查看原题

Natasha 最喜欢的数字是 $$$n$$$ 和 $$$1$$$,Sasha 最喜欢的数字是 $$$m$$$ 和 $$$-1$$$。有一天,Natasha 和 Sasha 见面并写下了每个可能的长度为 $$$n+m$$$ 的数组,使得其中一些 $$$n$$$ 元素等于 $$$1$$$,另外 $$$m$$$ 元素等于 $$$-1$$$。对于每个这样的数组,他们计算其最大前缀和,可能是一个等于 $$$0$$$ 的空前缀和(换句话说,如果每个非空前缀和都小于零,则它被视为等于零)。形式上,将长度为 $$$l \geq 0$$$ 的数组 $$$a_{1, \ldots ,l}$$$ 的最大前缀和表示为 $$$f(a)$$$。然后:

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

现在他们想要计算每个这样的数组的最大前缀和的总和,并且他们要求你帮忙。由于这个和可能非常大,因此输出它对 $$$998\: 244\: 853$$$ 取模。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$0 \le n,m \le 2\,000$$$)。

输出

输出对 $$$998\: 244\: 853$$$ 取模的问题答案。

示例

输入 #1

0 2

输出 #1

0

输入 #2

2 0

输出 #2

2

输入 #3

2 2

输出 #3

5

输入#4

2000 2000

输出#4

674532367

注意

在第一个示例中,唯一可能的数组是 [-1,-1],其最大前缀和等于 $$$0$$$。

在第二个示例中,唯一可能的数组是 [1,1],其最大前缀和等于 $$$2$$$。

第三个示例中有 $$$6$$$ 可能的数组:

[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

所以第三个例子的答案是$$$2+1+1+1+0+0 = 5$$$。