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].