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$

见题面

见题面