Contest Duration: - (local time) (200 minutes) Back to Home
D - Convex Sequence /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

• 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


入力例 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


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