Concatenation of two palindromes#9592
Find the number of ways to construct a string of length using Latin letters (the size of the alphabet is ) as the concatenation of two nonempty palindromes.
Two positive integers and k~(1 \le n \le 10^5, 1 \le k \le 26).
Print the number of ways to construct such a string. Print the answer modulo 10^9 + 7.
In the first test case the string of length using one letter ( for example) can be constructed in three ways: a + aaa, aa + aa, aaa + a.
Example 1
Example 2