dp[i][j][k] <- i 文字目まで見て S_i != T_i である index の個数が j 個で累積和が k となるような文字列 T の個数を計算して、行列累乗(実装が間に合いません)