Background

The full score for this problem is $110$.

Problem Description

Petar and Ivana felt bored on a long winter afternoon, so they invented a number game.

Petar randomly writes down $n$ numbers on paper. Each number is chosen independently and uniformly from $1$ to $k$, forming an array $a$.

Ivana says she especially likes some arrays because they have a kind of “hidden balance”. She calls such arrays structures (structure). The array $a$ is a structure if and only if the following conditions are satisfied:

• The integers $1,2,\dots,n$ each appear in the array exactly once.
• For every index $i$ ($1 \le i \le n$), we have $|a_i + i - n - 1| \le 1$.

Ivana wants to know: when Petar generates the array $a$ completely at random, what is the probability that it is a structure.

It can be proven that the answer can always be written as a fraction $\dfrac{P}{Q}$, where $P$ is an integer, and $Q$ is a positive integer that is not divisible by $10^9+7$.

Input Format

One line contains two non-negative integers $n,k$ ($1 \le n,k \le 10^9$).

Output Format

Output one integer, representing the required probability modulo $10^9+7$.

2 1

0

2 2

500000004

7 94

100976822

Hint

Sample Explanation

Explanation for Sample #2:

There are $2^2=4$ possible arrays Petar can write: $(1,1),(1,2),(2,1),(2,2)$. Among them, the structures are $(1,2)$ and $(2,1)$. The probability is $\dfrac{2}{4}$, so the output is $2 \cdot 4^{-1} \bmod (10^9+7)=500000004$.

Subtasks

Translated by ChatGPT 5