- Time limit: 2.00 s
- Memory limit: 512 MB
An integer sequence a_1,a_2,\dots,a_n is called quadratic if for all 1 \leq i < n, \left|a_{i} - a_{i+1}\right| = x^{2} for some integer x \geq 0.
Count the number of quadratic sequences of length n where each element is between 1 and m. Since the answer can be large, print it modulo 10^{9} + 7.
Input
The only input line has two integers n and m: the length of the sequence and the maximum value of every element in the sequence.
Output
Print the number of sequences modulo 10^{9} + 7.
Constraints
- 1 \leq n, m \leq 1000
Example
Input:
3 5
Output:
45
The sequences are as follows:
[1 1 1
], [1 1 2
], [1 1 5
], [1 2 1
], [1 2 2
],
[1 2 3
], [1 5 1
], [1 5 4
], [1 5 5
], [2 1 1
],
[2 1 2
], [2 1 5
], [2 2 1
], [2 2 2
], [2 2 3
],
[2 3 2
], [2 3 3
], [2 3 4
], [3 2 1
], [3 2 2
],
[3 2 3
], [3 3 2
], [3 3 3
], [3 3 4
], [3 4 3
],
[3 4 4
], [3 4 5
], [4 3 2
], [4 3 3
], [4 3 4
],
[4 4 3
], [4 4 4
], [4 4 5
], [4 5 1
], [4 5 4
],
[4 5 5
], [5 1 1
], [5 1 2
], [5 1 5
], [5 4 3
],
[5 4 4
], [5 4 5
], [5 5 1
], [5 5 4
], [5 5 5
].