Problem 27138 --公共DNA序列

27138: 公共DNA序列

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

Description

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中不一定连续。

Input

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

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

Output

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

Sample Input

GTC
3

Sample Output

1
37
25
1

HINT


数据范围:



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



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



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

Source

[Submit][Status]