Counting Strings by LCS with a Given Sequence

Given a string S consisting of characters from the set \(\{A, C, G, T\}\) and an integer m, consider all strings T of length m over the same alphabet.

Define \(\text{LCS}(S,T)\) as the length of the longest common subsequence between S and T. Note that the subsequence does not have to be contiguous.

Your task is: For each \(0 \le i \le |S|\), determine the number of strings T such that \(|\text{LCS}(S,T)| = i\). Since the answer can be huge, output your answers modulo \(10^9+7\).

Example: If S = "AC" and m = 2, one valid output is 4 5 7 meaning there are 4 strings T with LCS length 0, 5 with LCS length 1, and 7 with LCS length 2.

inputFormat

The first line contains the string S consisting of characters A, C, G, and T.

The second line contains an integer m — the length of the string T.

outputFormat

Output \(|S|+1\) space‐separated integers. The \(i\)-th integer (starting from \(i=0\)) should denote the number of strings T of length m with \(|\text{LCS}(S,T)| = i\), modulo \(10^9+7\).

sample

AC
2

4 5 7