### PROBLEM LINKS

### DIFFICULTY

SIMPLE

### PREREQUISITES

Simple Math, Matrix Exponentiation

### PROBLEM

Find the number of palindromic strings that can be made of length **N**, or less.

### QUICK EXPLANATION

We can fix the first **ciel(N/2)** characters of the string as we want, and the rest of the string is simply forced.

Also, each string we get by fixing the first **ciel(N/2)** characters is a unique palindromic string.

Thus, we can find the number of palindromic strings of each length

F(n) = 26^{ceil(n/2)}

Now, we need to find the summation of this result for all **n** from **1 to N** to find all the palindromic strings of length **N**, or less.

SUMMA( F(n), 1 ≤ n ≤ N ) = 2*SUMMA( 26^{n}, 1 ≤ n ≤ ceil(N/2) ), for even N 2*SUMMA( 26^{n}, 1 ≤ n ≤ floor(N/2) ) + 26^{ceil(N/2)}for odd N

We know that we can find **a ^{b}** for a large

**b**by repeated squaring. The problem now reduces to calculating the following

S(n) = SUMMA( 26^{n}, 1 ≤ n ≤ T )

### EXPLANATION

There are two ways to find the result.

**METHOD 1: Matrix Exponentiation**

S(n) = 26, for n = 1 = 26*S(n-1) + 26

We can build the matrix equation as below

| S(n+1) | = | 26 26 | * | S(n) | | 1 | | 0 1 | | 1 |

Thus, to find the result, we can calculate

| 26 26 |^{T}| 0 1 |

By repeated squaring of matrices. The results need to be found **modulo 1000000007**. Since all calculations are **sum** or **product** only, the drill should be straightforward.

**METHOD 2: Sum of Geometric Progression**

S(T) = 26*(26^{T}- 1) / 25

Calculating the numerator modulo 1000000007 is pretty straight forward. We use repeated squaring for the exponent part.

But, to the uninitiated it might be confusing as to why can we get away with calculating the residue of the numerator considering we are yet to divide it by 25.

Here, we apply the concept of modular arithmetic inverses. These are well defined for **residues modulo primes**. 1000000007 happens to be a prime (and is often the reason it is chosen in problems by several authors). The modular arithmetic inverse of **25, modulo 1000000007** is

25^{1000000005}

We arrive at this result by virtue of Fermat’s Little Theorem. Since

25^{1000000006}= 1, modulo 1000000007 25 * 25^{1000000005}= 1, modulo 1000000007 Thus, 25^{1000000005}= 25^{-1}, modulo 1000000007

Now, by using repeated squaring, we can find the modular inverse of **25** and multiply it to the numerator to find our answer.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.