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 .
Print the number of ways to construct the given string. Print the answer modulo .
In the first test case the string of length using one letter ( for example) can be constructed in three ways: .