Rohan loves Palindromes. Palindrome is a string that read same forward and backward. For example abba is a palindrome while abca is not.

Rohan is forming a palindrome of length lesser than or equal to n, with first k characters of lowercase English letters. He needs your help to find out the number of possible palindromes.

Output the result modulo 10⁹ + 7

Input Format

First line contains 2 space separated integers, n and k

Output Format

Output a single integer, which is answer to the problem

Constraints

• 1 ≤ n ≤ 10⁹
• 1 ≤ k ≤ 26