基因串

时间限制:10s      空间限制:128MB

题目描述

基因串是由ACGT4个字母组成的,我们有一个长度为n的基因串S。想要知道长度
为m的基因串中,与S的最长公共子序列分别为0, 1...n的串各有几个。
输出答案关于10^9+7的余数。


输入格式

第一行一个字符串S。第二行一个正整数m。


输出格式

n +1行,第i +1行表示与S公共子序列为i的串有几个关于10^9+7的余数。


样例输入

GTT
10

样例输出

1024
116050
434050
497452

提示

没有写明提示


题目来源

没有写明来源