以下では、\(S\) の \(i\) 文字目より右の部分 \(S_{i+1} S_{i+2} \ldots S_N\) で英小文字 \(c\) が現れる最も左の位置を \(\sigma(i, c)\) で表します。 ただし、\(S\) の \(i\) 文字目より右に \(c\) が現れない場合は \(\sigma(i, c) \coloneqq \infty\) とします。

本問題は、\(S\) の非空な部分列であって、ある文字列 \(T\) によって \(TT\) と表されるものの個数（種類数）を求める問題です。

入力例２の説明文にもあるように、ある文字列 を \(S\) から部分列として取り出す方法は複数存在し得るため、各部分列を複数回数えてしまわないように工夫が必要です。 そこで、部分列を \(S\) から取り出す際には

（\(\spadesuit\)）： \(S\) の中でできるだけ左にある文字から優先的に取り出す

というルールを課すことにします。 つまり、部分列 \(TT = T_1T_2\ldots T_nT_1T_2\ldots T_n\) を \(S\) から取り出す際には、

まず、\(TT\) の前半の \(T\) に対応して、

• \(p_1 \coloneqq \sigma(0, T_1)\) として、\(S\) の \(p_1\) 文字目を取り出し、
• \(p_2 \coloneqq \sigma(p_1, T_2)\) として、\(S\) の \(p_2\) 文字目を取り出し、
• \(p_3 \coloneqq \sigma(p_2, T_3)\) として、\(S\) の \(p_3\) 文字目を取り出し、
• \(\cdots\)
• \(p_n \coloneqq \sigma(p_{n-1}, T_n)\) として、\(S\) の \(p_n\) 文字目を取り出す。

続けて、\(TT\) の後半の \(T\) に対応して、

• \(q_1 \coloneqq \sigma(p_n, T_1)\) として、\(S\) の \(q_1\) 文字目を取り出し、
• \(q_2 \coloneqq \sigma(q_1, T_2)\) として、\(S\) の \(q_2\) 文字目を取り出し、
• \(q_3 \coloneqq \sigma(q_2, T_3)\) として、\(S\) の \(q_3\) 文字目を取り出し、
• \(\cdots\)
• \(q_n \coloneqq \sigma(q_{n-1}, T_n)\) として、\(S\) の \(q_n\) 文字目を取り出す。

という流れになります。

このルールによって、\(S\) の各部分列に対してその取り出し方が唯一に定まるため、各部分列 \(TT\) を \(1\) 回ずつ重複なく数え上げることができます。 その具体的な方針として、まず整数 \(x\) を固定し、

（\(\star\)）：ルール（\(\spadesuit\)）にしたがって \(S\) から取り出す際に \(q_1 = x\) となるような部分列 \(TT\) の個数

を数えることを以下で考えます。 \(q_1\) として考えられるすべての位置 \(x\) にわたる上記（\(\star\)）の総和を求めれば、本問題の答えが得られます。

\(q_1 = x\) と固定するとき、\(T_1 \coloneqq S_x\) および \(p_1 \coloneqq \sigma(0, T_1) = \sigma(0, S_x)\) と決定されます。 その初期状態からはじめ、\(T\) の \(2\) 文字目以降を先頭から順に決定していきながら、\(p_1\) を起点として \(TT\) の前半の \(T\) を、\(q_1\) を起点として \(TT\) の後半の \(T\) を、それぞれ \(S\) から並列に取り出していくこと考えます。 具体的には、

• まず、\(T_2\) をどの英小文字にするか決定し、\(p_2 = \sigma(p_1, T_2), q_2 = \sigma(q_1, T_2)\) として、\(S\) の \(p_2\) 文字目と \(q_2\) 文字目をそれぞれ取り出す。
• 次に、\(T_3\) をどの英小文字にするか決定し、\(p_3 = \sigma(p_2, T_2), q_3 = \sigma(q_2, T_3)\) として、\(S\) の \(p_3\) 文字目と \(q_3\) 文字目をそれぞれ取り出す。
• \(\cdots\)
• 次に、\(T_n\) をどの英小文字にするか決定し、\(p_n = \sigma(p_{n-1}, T_n), q_n = \sigma(q_{n-1}, T_n)\) として、\(S\) の \(p_n\) 文字目と \(q_n\) 文字目をそれぞれ取り出す。

といった流れになります。 （\(\star\)）を求めるには、上記の過程で作られる文字列 \(T\) であって、\(\sigma(p_n, T_1) = q_1\) （ルール（ \(\spadesuit\) ）を満たすための必要条件）を満たすものの個数を求めれば良いです。

これは動的計画法（ DP ）によって求められます。具体的には、DP テーブルを

\(dp[i][j] = \)（ \(p_n = i, q_n = j\) となるような \(T = T_1T_2\ldots T_n\) の個数）

とおき、各 \((i, j)\) について、\(T\) の \(n+1\) 文字目 \(T_{n+1}\) をどの英小文字 \(c = \) a, b, \(\ldots\), z にするかに対応した

\(dp[\sigma(i, c)][\sigma(j, c)] \leftarrow dp[\sigma(i, c)][\sigma(j, c)] + dp[i][j]\)

という \(26\) 本の遷移を行えば良いです（ただし、\(\sigma(i, c) = \infty\) または \(\sigma(j, c) = \infty\) となる \(c\) は無視します）。

所望の（\(\star\)）は \(\sigma(p_n, T_1) = q_1\) を満たす \(T\) の個数、すなわち、\(\sum_{\sigma(i, S_x) = x}\sum_j dp[i][j]\) として得られます。

この DP における時間計算量は、文字の種類数（本問題では \(26\) ）を \(\Sigma\) とおくと \(O(N^2\Sigma)\) 時間であり、 これを \(q_1\) として考えられるすべての位置 \(x\) （ \(O(N)\) 通り）について行うと、アルゴリズム全体で \(O(N^3\Sigma)\) 時間で本問題を解くことができます。