#P4258. 基因串

基因串

基因串

题目描述

基因串由 A、C、G、T 四种字符组成。已知基因串 SS,其长度为 nn。对每个 k=0,1,…,nk=0,1,\ldots,n,求有多少个长度为 mm 的基因串与 SS 的最长公共子序列长度恰好为 kk。答案对 109+710^9+7 取模。

子序列保留字符原来的相对顺序,可以跳过字符。

输入格式

第一行一个非空基因串 SS。第二行一个正整数 mm。

输出格式

输出 n+1n+1 行。第 k+1k+1 行表示最长公共子序列长度恰为 kk 的基因串数量对 109+710^9+7 取模的结果。

样例 #1

样例输入 #1

GTT
10

样例输出 #1

1024
116050
434050
497452