After CC set up several questions, he invited Little Horse to check the difficulties. Although Little Horse is very clever and quickly came up with ideas to solve the questions, he thought they may be slightly difficult for most contestants. So he is adding an easy question.

Little Horse has a string \(S\) which only consists of lowercase letters, and he is asking you about the string. In each query, Little Horse gives an integer \(i\), meaning that he cut \(S\) into two parts between the \(i\)-th and \((i+1)\)-th characters. So we get two substrings \(S[1,i]\) and \(S[i+1, |S|]\). Denote \(A=S[1,i], B=S[i+1, |S|]\). Now, considering all the consecutive substrings of \(A\) and all the consecutive substrings of \(B\), Little Horse wants to know how many pairs of same substrings are there between \(A\) and \(B\). Formally, he wants to know:

\[

ans = \sum_{1\leq l_1\leq r_1\leq |A|} \sum_{1\leq l_2\leq r_2\leq |B|} [\space A[l_1, ..., r_1] == B[l_2, ..., r_2] \space]

\]

where

\[

[x] = \begin{cases}

1 \space(x=True) \\

0 \space(x=False)

\end{cases}

\]

Could you help Little Horse?