Removable Sequence Count

Given two integers \(n\) and \(m\), count the number of sequences of length \(n\) such that:

1. Each element is an integer in the range [1, \(m\)].
2. An operation is defined as deleting a contiguous subsequence of length at least 2 whose first and last elements are equal. It is guaranteed that after a sequence of such operations the sequence can be completely removed.

The answer should be given modulo \(10^9+7\).

Note: A sequence is valid (removable) if it can be reduced to an empty sequence by repeatedly deleting segments that start and end with the same value. It can be shown that a necessary and sufficient condition is that \(n\) is even and if we set \(p = n/2\), then the number of valid sequences equals
\( \text{Catalan}(p)\times m^p \),
where the \(p^{th}\) Catalan number is given by \( \displaystyle C_p = \frac{1}{p+1}\binom{2p}{p} \).

inputFormat

The input consists of a single line containing two integers \(n\) and \(m\) separated by a space.

Constraints:

• \(1 \leq n, m \leq 10^5\) (for example)

outputFormat

Output a single integer, the number of valid sequences modulo \(10^9+7\).

sample

1 5

0