# PROBLEM LINK:

Authors: Sahil Grover

Testers: Vaibhav Daga

Editorialist: Sahil Grover

# DIFFICULTY:

Easy

# PREREQUISITES:

Basic math, Sweg

# PROBLEM:

We need to find the number of strings of length N made by using at most K alphabets such that every substring of length exactly equal to M is a palindrome.

# EXPLANATION:

In this problem we have to consider 5 cases:

if M > N : No substring of length M is possible in a string of length N so we simply print “Sweg”(without quotes).

if M = 1 : Any string of length N is possible so the answer is K^N.

if M = N : The string itself must be a palindrome. So the answer will be K^((N+1)/2) (’/’ implies integer division).

if 1 < M < N :

if M is odd, the answer will be K^2.

if M is even, the answer will be K.

The answer can be evaluated using Recursive Modular Exponentiation.

# Time Complexity:

Worst case time complexity for each test case will be O(log N) (when M = 1 ).

# AUTHOR’S SOLUTION:

Author’s solution can be found here