### Problem link

### Difficulty

SIMPLE

### Pre-requisites

small fact about palindromes

### Problem

Find out the number of strings of length N having alphabet size <= M such that it does not contain any palindrome as a substring. Print the answer modulo 1000000007 (10^9 + 7).

### Solution

**Observation 1**

If a large string is palindrome, you can remove one character from left and right, still the string will remain a palindrome. this property will always hold for any palindromic string of length >= 3.

So from this observation, you can see that we just have to make sure that there are no palindromes of length 2 and 3.

**Combinatorics**

So we will start from left to right and try creating valid strings of length N. We can fill first position in M ways (use any character in the alphabet set). Then for the second position,

you can not use the previous character, so there are M - 1 choices. For third position, you can not use both first and second position characters, so there are M - 2 choices.

For any position >= 3, you can see that there will be M - 2 choices.

**Final formula**

- If N = 1, then M
- If N = 2, then M * (M - 1).
- If N >= 3, then M * (M - 1) * (M - 2)
^{ (N - 2)}.

**Calculating a^b % mod**

You can use binary exponentiation idea to solve it in O(log N).

**Time Complexity**

O(log(N)) in computing modular exponentiation.

**Testerâ€™s solution**: Will be added Later