Note:This is my first editorial and i am still a noob in first year of my college so please forgive me for any mistakes.Also suggestions are welcome.

## Contest link

**Problem:**

**PRE-REQUISITES:**

Basic Combinatronics, Basic Probability, Inverse Modulo, Fermat’s Little Theorem, Fast exponentiation

**PROBLEM:**

Bob has a string (S), which is initially empty. In one operation, he can select a lowercase character (a-z) uniformly at random and appends it to S. He then evaluates whether S is a palindrome or not; if it is, he gets 1 point.

Given that Bob performs N operations in total, find the expected no. of points Bob gets. It is guaranteed that the answer can always be represented as a rational number a/b

**EXPLANATION:**

- WE WILL DISCUSS THE SOLUTION WHICH FETCHES 100 POINTS

What we basically have to do is find number of palindromic strings in a string of size **N**. What we find is that if **N** is odd, number of such strings is 26^((**N**/2)+1) and 26^(**N**/2) if even.Let this be **P**.

Also number of all possible strings is 26^**N**.

Next thing is for a particular **N** expected value of palindromic string is **P**/((26)^**N**).

Next observation is that while constructing a string of size **N** we also have to take into consideration all string of size **K** (1<=**K**<=**N**).

Thus we get a series of the form

```
1+ 1/26 +1/26 + 1/(26^2)+ 1/(26^2) + 1/(26^3) + 1/(26^3) + 1/(26^4) + 1/(26^4) .... upto N terms.
```

The next task is to represent it in the form **a**/**b**.

To do this we first take a look at **b**

After adding the terms we find **b** is 26^**X** where **X** is higest power of 26 in the series.

Similarly we find **a** is something like

```
26^x +2.(26^(x-1))+....+(J).1
```

Where **J** is 1 if n is even else 2.

This can be represented as a sum of **G.P.** series with some constraints. Use little fermat’s along with fast exponentiation here in calculating the series sum.

Now we are left with **(a/b)**% 1000000007.

This can be calculated easily using little fermats theorem.