def solve(self, cipher):
        """
        Any palindrome, it has a sub-palindrome with length 2 or 3 pivoting at the center.

        To construct a palindrome, the 1st letter has M ways, the 2nd has (M-1) ways, subsequently, there
        are (M-2) ways to choose letters, since it should not be the same as the previous or pre-previous letter;
        otherwise it will form a palindrom with either length 2 or 3.

        Therefore, total = M*(M-1)*(M-2)*(M-2)*(M-2)...

        :param cipher: the cipher
        """
        N, M = cipher
        s = M
        if N > 1:
            s *= (M - 1)
        if N > 2:
            s *= pow(M - 2, N - 2, MOD)  # s *= self._exp(M-2, N-2)
            s %= MOD
        return s % MOD
dataset/ETHPy150Open algorhythms/HackerRankAlgorithms/AntiPalindromic Strings.py/Solution.solve/original