Make a graph with vertexes 1, 2, ..., n; for each i a substring s_is_i + 1...s_{i + k - 1} should be a palindrome, so for each i you should make edges between s_i and s_{i + k - 1}, between s_i + 1 and s_{i + k - 2}, etc. For each connected component in this graph, letters should be equal in each vertex of that component; if number of components is e then the answer is m^e