Problem Description

Given $n$ and $m$, find the number of sequences of length $n$ that satisfy the following conditions:

1. Each element is between $[1, m]$.
2. One operation is defined as deleting an interval of length at least $2$ whose two endpoints are equal. The sequence must be able to be completely deleted using several operations.

Output the answer modulo $10^9 + 7$.

Input Format

The first line contains two positive integers $n$ and $m$.

Output Format

Output one integer, which is the result modulo $10^9 + 7$.

4 2

10

Hint

Sample Explanation

The valid sequences are:

$[1,1,1,1]$

$[1,1,2,1]$

$[1,1,2,2]$

$[1,2,1,1]$

$[1,2,2,1]$

$[2,1,1,2]$

$[2,1,2,2]$

$[2,2,1,1]$

$[2,2,1,2]$

$[2,2,2,2]$

Constraints

$1 \le n \le 3000$，$1 \le m \le 10^9$。

Translated by ChatGPT 5