Candy Removal Dream

In a strange dream, Coco sees a row of n candies, each having a color represented by an integer in the range \( [1, m] \). In one move, Coco may choose two candies of the same color and eat them along with every candy between them. Coco recalls that there exists at least one way to eat all the candies in the dream using a sequence of such moves.

Your task is to count, among all \( m^n \) possible candy sequences, how many sequences could have been in Coco's dream (i.e. sequences for which there exists a valid removal order that eats all candies). Output the answer modulo \(10^9+7\).

Removal Process Explanation: A sequence \( S = s_1,s_2,\dots,s_n \) is said to be removable if and only if \( n \) is even and there exists an index \( j \) (with \( 2\le j\le n \)) such that \( s_1 = s_j \), the substring \( s_2,\dots,s_{j-1} \) is removable, and the remaining substring \( s_{j+1},\dots,s_n \) is removable. (By convention, the empty sequence is removable.)

This recurrence implies that any removable sequence has a unique canonical decomposition obtained by taking the smallest possible \( j \) for which \( s_1=s_j \) and the block in between does not contain \( s_1 \). In other words, if we denote by \( F(n; k) \) the number of removable sequences of length \( n \) over an alphabet of size \( k \), then for \( n=0 \), \( F(0; k)=1 \), and for even \( n\ge2 \) we have:

[ F(n; m)= \sum_{\substack{j=2 \ j ;\text{even}}}^{n}; m\cdot F(j-2; m-1)\cdot F(n-j; m), ]

For odd \( n \) the answer is 0. You are asked to compute \( F(n; m) \) modulo \( 10^9+7 \).

inputFormat

The first line of input contains two space‐separated integers \( n \) and \( m \), representing the number of candies and the number of colors respectively.

outputFormat

Output a single integer – the number of dream sequences that can be completely removed, taken modulo \(10^9+7\).

sample

2 1

1