403667: GYM101237 D Short Enough Task

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Short Enough Tasktime limit per test0.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExamplesInput
3 2
Output
4.5000000000
Note

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

加入题单

上一题 下一题 算法标签: