Chain#3675
The chain is made up of links, each painted in one of 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.
The input file provides the numbers and (1 \le N \le 10^9, 1 \le K \le 10^9).
Output the number of distinct chains consisting of links, each painted in one of colors. If the result exceeds , output only the last nine digits of the number.
Example 1