Mathematical explanation The points (or gain) for each win is $X_l=1$ where $l$ is the length of the String. (Points for loss is $0$). Expectation is the weighted sum of the points, the weights being the probability of each event. Precisely, the expected number of points for $N$length palindrome is $E_N=\sum_{i=1}^{N} P_iX_i=\sum_{i=1}^NP_i$ , where $P_i$ is the probability to get the string with length=$i$ as a palindrome. So we have to calculate $P_l$. Consider a string of length $l$. The sample space is of size $26^l$ as we have 26 character choices for every position. If $l$ is odd, then number of palindromes of length $l$ is $26^{l+1\over 2}$ [Just decide the characters of the positions $1,2,\dots, {l+1\over 2}$ and the remainder spaces are filled symmetrically]. If $l$ is even, then it is enought to fill the positions $1,2,\dots,l/2$ and fill the remainder symmetrically to get palindrome. So we have $P_k= \left\{{26^{1k\over 2}, 2\notk \\ 26^{{k\over 2}},2k} \right. $ So, we observe that $P_k=26^{\left\lfloor {k\over 2} \right\rfloor }$ $\mathbb{1:}\\E_N=P_1+P_2+\dots +P_N=\left\{ {1+2\left(26^{1}+26^{2}+\dots+26^{\left\lfloor {k\over 2} \right\rfloor }\right), \textrm{ if }2\notN \\ 1+2\left(26^{1}+26^{2}+\dots+26^{\left\lfloor {k\over 2} \right\rfloor+1}\right)+26^{\left\lfloor {k\over 2} \right\rfloor }, \textrm{ if } 2N}\right.$ Let $x=\lfloor k/2 \rfloor$. After simplyfying we will have, $\mathbb{2:}\\E_N=\left\{ {1+2\cdot\frac{26^x1}{26^x\cdot 25}, \textrm{ if }2\notN \\ 1+2\cdot\frac{26^x1}{26^x\cdot 25}\frac{1}{26^x}, \textrm{ if }2N} \right.$ To compute the inverses, we have to use Fermat's little theorem: $a^{p1}\equiv 1\pmod p\forall a\in \mathbb{N}, (a,p)=1$ So we will have the two parts of expression $(2)$ as congruent to $\left(1+2\cdot(26^x1)\cdot25^{p2}\cdot26^{p1x}\right)\pmod p$ and $\left(1+2\cdot(26^x1)\cdot25^{m2}\cdot26^{m1x}26^{p1x}\right)\pmod p$ Coding To use make the above computation faster, use the modular exponentiation. This is suitable as $10^9+7$ is prime. Here goes the code for 50 points wherein the computation has been done with the expression labelled as $1$: Partial Here goes the code for 100 points using simplified expression labelled as $2$: Full asked 02 May '18, 21:35
