/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
長さ N+1 の数列 A = (A_1,A_2, \ldots, A_{N + 1}) に対して、以下のような方法で長さ N の数列 S = (S_1, S_2, \ldots, S_{N}) を得ることを考えます。
- 各 i (1 \le i \le N) について、 S_i=A_i+A_{i + 1} とする。
以下の条件を全て満たす長さ N の数列 S の個数を 10^9 + 7 で割った余りを求めて下さい。
- 広義単調増加である。
- ある 0 以上 M 以下の整数からなる長さ N+1 の数列 A であって、A から前述の方法で S を得ることができるものが存在する。
制約
- 1 \le N, M \le 10^7
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを 1 行に出力せよ。
入力例 1
2 1
出力例 1
5
A として考えられるのは以下の 8 通りです。
- A = (0,0,0) のとき、S = (0,0)
- A = (0,0,1) のとき、S = (0,1)
- A = (0,1,0) のとき、S = (1,1)
- A = (0,1,1) のとき、S = (1,2)
- A = (1,0,0) のとき、S = (1,0)
- A = (1,0,1) のとき、S = (1,1)
- A = (1,1,0) のとき、S = (2,1)
- A = (1,1,1) のとき、S = (2,2)
このうち広義単調増加な S は、(0,0),(0,1),(1,1),(1,2),(2,2) の 5 種類です。
入力例 2
869121 10000000
出力例 2
767557322
Score : 600 points
Problem Statement
For a sequence A = (A_1, A_2, \ldots, A_{N+1}) of length N+1, consider obtaining a sequence S = (S_1, S_2, \ldots, S_N) of length N in the following way.
- For each i (1 \le i \le N), let S_i = A_i + A_{i+1}.
Find the number, modulo 10^9 + 7, of sequences S of length N satisfying all of the following conditions.
- S is non-decreasing.
- There exists a sequence A of length N+1 consisting of integers between 0 and M, inclusive, such that S can be obtained from A in the way described above.
Constraints
- 1 \le N, M \le 10^7
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Output the answer on a single line.
Sample Input 1
2 1
Sample Output 1
5
The possible sequences A are the following eight:
- A = (0,0,0), for which S = (0,0)
- A = (0,0,1), for which S = (0,1)
- A = (0,1,0), for which S = (1,1)
- A = (0,1,1), for which S = (1,2)
- A = (1,0,0), for which S = (1,0)
- A = (1,0,1), for which S = (1,1)
- A = (1,1,0), for which S = (2,1)
- A = (1,1,1), for which S = (2,2)
Among these, we have five distinct non-decreasing S: (0,0),(0,1),(1,1),(1,2),(2,2).
Sample Input 2
869121 10000000
Sample Output 2
767557322