Chain

The chain is made up of N links, each painted in one of K colors. Let's consider two such chains. For each chain, we choose one of the end links and list the colors of all the links in sequence starting from that link. We will consider these chains identical if they produce the same sequence of colors.

Your task is to determine the number of distinct chains.

Input

The input file provides the numbers N and K (1 ≤ N ≤ 10^9, 1 ≤ K ≤ 10^9).

Output

Output the number of distinct chains consisting of N links, each painted in one of K colors. If the result exceeds 999999999, output only the last nine digits of the number.

Examples