CF578D LCS Again

给定一个字符串 $S$，求有多少个与 $S$ 等长字符串 $T$，满足 $\mathrm{LCS}(S,T)=|S|-1$，其中 $S,T$ 只包含前 $m$ 个小写字母。

无

无

For the first sample, the $ 6 $ possible strings $ T $ are: aab, aac, aba, aca, baa, caa. For the second sample, the $ 11 $ possible strings $ T $ are: aaa, aac, aba, abb, abc, aca, acb, baa, bab, caa, cab. For the third sample, the only possible string $ T $ is b.