Let us briefly review how we can find the length of a Longest Common Subsequence (LCS) of \(T\) and \(S\).

Prepare an array \(dp\) (DP stands for Dynamic Programming) of size \((|T|+1)\times (|S|+1)\), where \(dp[i][j]\) represents the length of a LCS of \(T[:i]\) and \(S[:j]\). There are three kinds of transitions:

1. \(dp[i][j] \leftarrow dp[i-1][j]\)
2. \(dp[i][j] \leftarrow dp[i][j-1]\)
3. \(dp[i][j] \leftarrow dp[i-1][j-1]+1\) if \(T[i]=S[j]\)

Taking a closer look at the transitions, we notice the following properties of the DP array:

• \(dp[i][0]=0\)
• \(0\leq dp[i][j+1]-dp[i][j]\leq 1\)

That is, \(dp[i]\) is a weakly monotonically increasing sequence where adjacent elements differ at most by one. Thus, there are only \(dp[i]\) possible patterns for \(2^{|S|}\).

We use this fact to solve the original problem. Let \(DP[i][dp\_array]\) be the number of strings \(T\) of length \(i\) such that \(dp\_array\) is the DP array \(dp[i]\) when finding an LCS of \(T\) and \(S\). The updates on \(dp\_array\) as \(i\) increases can be found according to the transitions of the DP for LCS described above. There are \(O(2^N)\) states for \(DP[i]\), and computing transitions of \(dp\_array\) costs \(O(\sigma N)\), so the overall complexity is \(O(NM\sigma 2^N)\) (where \(\sigma\) is the size of alphabet). By precalculating the transitions, the complexity can be reduced to \(O(NM2^N)\).

from collections import defaultdict

mod = 998244353

N, M = map(int, input().split())
A = [ord(i) - ord("a") for i in input()]
K = 26
dp = defaultdict(int)
dp[tuple([0] * (N + 1))] = 1
for _ in range(M):
    ndp = defaultdict(int)
    for arr, c in dp.items():
        for i in range(K):
            narr = [0] * (N + 1)
            for j in range(N):
                narr[j + 1] = max(narr[j], arr[j + 1])
                if A[j] == i:
                    narr[j + 1] = max(narr[j + 1], arr[j] + 1)
            ndp[tuple(narr)] = (ndp[tuple(narr)] + c) % mod
    dp = ndp
ans = [0] * (N + 1)
for arr, c in dp.items():
    ans[arr[N]] += c
print(*[i % mod for i in ans])