← 返回题目列表

AtCoder · agc049_d

D. 凸序列

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

分数: 1000 点

问题陈述

给定的是整数 N 和 M。 求模数 (10^9+7),长度-N 序列 (A_1,A_2,\ldots,A_N) 由非负整数组成并满足以下条件:

  • A_1+A_2+\ldots +A_N = M;
  • 对于每个 i (2 \leq i \leq N-1), 2 A_i \leq A_{i-1} + A_{i+1}.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M

输出

打印数字,模数 (10^9+7),满足条件的序列。


示例输入 1

3 3

示例输出 1

7

以下七个序列满足条件。

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

示例输入 2

10 100

示例输出 2

10804516

示例输入 3

10000 100000

示例输出 3

694681734