CF578D LCS Again

You are given a string $ S $ of length $ n $ with each character being one of the first $ m $ lowercase English letters. Calculate how many different strings $ T $ of length $ n $ composed from the first $ m $ lowercase English letters exist such that the length of LCS (longest common subsequence) between $ S $ and $ T $ is $ n-1 $ . Recall that LCS of two strings $ S $ and $ T $ is the longest string $ C $ such that $ C $ both in $ S $ and $ T $ as a subsequence.

N/A

N/A

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.