Shashank hates palindromes. Palindrome is a string that can be read the same way in either direction, from the left to the right and from the right to the left.

Shashank is trying to construct awesome strings. Awesome string is the string such that it doesn't contain any palindrome contiguous substring of length 2 or more. Each of the character in string is one of the first p letters of the English alphabet.

Length of awesome string should be n.
You need to help Shashank by finding out the number of possible Awesome strings.

Output the result modulo 10⁹ + 7.

Input Format

First line contains 2 space separated integers, n and p

Output Format

Output a single integer, which is answer to the problem

Constraints

• 1 ≤ n ≤ 10¹⁸
• 1 ≤ p ≤ 26