Solve the programming task below in a Python markdown code block.
A border of a string is a proper prefix of it that is also a suffix. For example:

a and abra are borders of abracadabra,
kan and kankan are borders of kankankan. 
de is a border of decode. 

Note that decode is not a border of decode because it's not proper.

A palindromic border is a border that is palindromic. For example,

a and ana are palindromic borders of anabanana, 
l, lol and lolol are palindromic borders of lololol.

Let's define $P(s)$ as the number of palindromic borders of string $\boldsymbol{\mathrm{~s~}}$. For example, if $\boldsymbol{s}=$ lololol, then $P(s)=3$. 

Now, a string of length $N$ has exactly $N(N+1)/2$ non-empty substrings (we count substrings as distinct if they are of different lengths or are in different positions, even if they are the same string). Given a string $\boldsymbol{\mathrm{~s~}}$, consisting only of the first 8 lowercase letters of the English alphabet, your task is to find the sum of $P(s^{\prime})$ for all the non-empty substrings ${s'}$ of $\boldsymbol{\mathrm{~s~}}$. In other words, you need to find:
$\sum\limits_{1\leq i\leq j\leq N}P\left(s_{i\ldots j}\right)$
where $s_{i\ldots j}$ is the substring of $\boldsymbol{\mathrm{~s~}}$ starting at position $\boldsymbol{i}$ and ending at position $j$.

Since the answer can be very large, output the answer modulo $10^9+7$.

Input Format  

The first line contains a string consisting of $N$ characters.

Output Format  

Print a single integer: the remainder of the division of the resulting number by $10^9+7$.

Constraints  

$1\leq N\leq10^5$ 

All characters in the string can be any of the first 8 lowercase letters of the English alphabet (abcdefgh).  

Sample Input 1  

ababa

Sample Output 1  

5

Sample Input 2  

aaaa

Sample Output 2  

10

Sample Input 3  

abcacb

Sample Output 3  

3

Explanation  

$\boldsymbol{s}=$ ababa has 15 substrings but only 4 substrings have palindromic borders.  

$s_{1\ldots3}=$ aba    $\longrightarrow P(s_{1\ldots3})=1$ 

$s_{1\ldots5}=$ ababa  $\longrightarrow P(s_{1...5})=2$ 

$s_{2\ldots4}=$ bab    $\longrightarrow P(s_{2\ldots4})=1$ 

$s_{3\ldots5}=$ aba    $\rightarrow P(s_{3\ldots5})=1$