403667: GYM101237 D Short Enough Task

Do you like expected values as much as we do? Then this problem and the next one are dedicated to you!

Let us generate a random string using the following algorithm: each of N characters of the random string is equiprobably chosen from the alphabet of size K.

Your task is to calculate the expected number of subpalindromes in such a random string.

The input contains two integers N and K, the length of the string and the size of the alphabet respectively (1 ≤ N, K ≤ 10⁹).

Output the expected number of subpalindromes. Your answer will be considered correct if its absolute or relative error is less than 10^- 6.

3 2

4.5000000000

As you remember, a subpalindrome is a non-empty substring of the original string that can be read identically in both directions.