Petar and Ivana are bored during a long winter afternoon, so they decided to invent a game with numbers.

Petar takes a sheet of paper and randomly writes down ~n~ numbers. Each number is chosen completely at random and independently among the integers from ~1~ to ~k~. Using this procedure, Petar creates an array ~a~ of ~n~ numbers.

Ivana says that she especially likes some arrays because they have a "hidden balance", and she calls them structures. An array is a structure if the following conditions are satisfied:

• Every number from ~1~ to ~n~ appears in the array exactly once.
• For every index ~i~ ~(1 \le i \le n)~, it holds that ~\lvert a_i + i - n - 1\rvert \le 1~.

Ivana is interested in the probability that Petar, choosing the numbers completely at random, constructs an array that is a structure.

It can be proven that the answer can always be represented as a fraction ~\frac{P}{Q}~, where ~P~ is an integer and ~Q~ is a positive integer not divisible by ~10^9 + 7~. In that case, output ~P \cdot Q^{-1} \pmod {10^9 + 7}~.

Input Specification

The first line contains the natural numbers ~n~ and ~k~ ~(1 \le n, k \le 10^9)~, the numbers from the problem statement.

Output Specification

Output a single number, the answer to the question from the problem statement.

Constraints

Subtask	Points	Constraints
~1~	~17~	~n, k \le 7~
~2~	~23~	~n \le 7 , k \le 100~
~3~	~19~	~n \le 20 , k \le 100~
~4~	~25~	~n, k \le 10^6~
~5~	~26~	No additional constraints.

Sample Input 1

2 1

Sample Output 1

0

Sample Input 2

2 2

Sample Output 2

500000004

Explanation for Sample Output 2

The arrays ~a~ that Petar can construct are: ~(1, 1),(1, 2),(2, 1), (2, 2)~. The arrays that are structures are ~(1, 2)~ and ~(2, 1)~. The probability that Petar completely at random obtains an array that is a structure is ~\frac{2}{4}~ , i.e. ~500\,000\,004 \pmod{10^9 + 7}~.

Sample Input 3

7 94

Sample Output 3

100976822