问题 27138 --公共DNA序列

27138: 公共DNA序列

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

Lxhgww的国家里,每个人的DNA都是一个长度为n的字符序列,其中的每一个字符都是'A', 'C', 'T', 'G'中的一个。例如ACGGT就是一个长度为5DNA序列。

 

已知Lxhgww的国家里,每个人的DNA序列都是不同的,并且一共有4^n个人。

 

现在Lxhgww有一个长度为mDNA序列S,现在Lxhgww想知道在他的国家里,对于每一个[0, m]内的每一个k,有多少个人的DNA序列T满足LCS(S, T) = k

 

其中,LCS(S, T)表示ST的最长公共子序列。子序列在ST中不一定连续。

输入

第一行读入一个字符串S,表示一个DNA序列。

第二行读入一个整数n,表示Lxhgww国家内每个人的DNA序列的长度。

输出

对于每一个k = 0, 1, ..., |S|,输出答案 % 1000000007,每个答案占一行。

样例输入

GTC
3

样例输出

1
37
25
1

提示


数据范围:



对于20%的数据,1 <= |S| <= 10, 1 <= n
<= 9



对于60%的数据,1 <= |S| <= 15, 1 <= n
<= 100



对于100%的数据,1 <= |S| <= 15, 1 <= n
<= 1000

来源

[提交][状态]