D - Convex Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

整数 N と M が与えられます． 長さ N の非負整数列 (A_1,A_2,\ldots,A_N) であって，次の条件を満たすものの個数を\bmod (10^9+7) で求めてください．

  • 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

出力

条件を満たす数列の個数を\bmod (10^9+7) で出力せよ．

入力例 1

3 3

出力例 1

7

以下の 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

Score : 1000 points

Problem Statement

Given are integers N and M. Find the number, modulo (10^9+7), of length-N sequences (A_1,A_2,\ldots,A_N) that consist of non-negative integers and satisfy the following conditions:

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

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number, modulo (10^9+7), of sequences that satisfy the conditions.

Sample Input 1

3 3

Sample Output 1

7

The following seven sequences satisfy the conditions.

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

Sample Input 2

10 100

Sample Output 2

10804516

Sample Input 3

10000 100000

Sample Output 3

694681734