AT_agc049_d [AGC049D] Convex Sequence

题目描述

给定整数 $N$ 和 $M$。请计算满足以下条件的长度为 $N$ 的非负整数序列 $(A_1, A_2, \ldots, A_N)$ 的个数，并对 $10^9+7$ 取模。

• $A_1 + A_2 + \ldots + A_N = M$。
• 对于所有 $i$（$2 \leq i \leq N-1$），都有 $2A_i \leq A_{i-1} + A_{i+1}$。

输入格式

输入从标准输入读取，格式如下：

$N$ $M$

输出格式

输出满足条件的序列个数，对 $10^9+7$ 取模。

样例 1

输入

3 3

输出

7

样例 2

输入

10 100

输出

10804516

样例 3

输入

10000 100000

输出

694681734

说明/提示

限制

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• 输入均为整数。

样例解释 1

以下 $7$ 个序列满足条件：

• $0,0,3$
• $0,1,2$
• $1,0,2$
• $1,1,1$
• $2,0,1$
• $2,1,0$
• $3,0,0$

由 ChatGPT 4.1 翻译