F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Hero meet devil

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1549    Accepted Submission(s): 770


Problem Description
There is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he is just like a boy in love and can¡¯t refuse any request from the devil. Also, this devil is looking like a very cute Loli.

After the ring has been destroyed, the devil doesn't feel angry, and she is attracted by z*p's wisdom and handsomeness. So she wants to find z*p out.

But what she only knows is one part of z*p's DNA sequence S leaving on the broken ring.

Let us denote one man's DNA sequence as a string consist of letters from ACGT. The similarity of two string S and T is the maximum common subsequence of them, denote by LCS(S,T).

After some days, the devil finds that. The kingdom's people's DNA sequence is pairwise different, and each is of length m. And there are 4^m people in the kingdom.

Then the devil wants to know, for each 0 <= i <= |S|, how many people in this kingdom having DNA sequence T such that LCS(S,T) = i.

You only to tell her the result modulo 10^9+7.
 

Input
The first line contains an integer T, denoting the number of the test cases.
For each test case, the first line contains a string S. the second line contains an integer m.

T<=5
|S|<=15. m<= 1000.
 

Output
For each case, output the results for i=0,1,...,|S|, each on a single line.
 

Sample Input
1 GTC 10
 

Sample Output
1 22783 528340 497452
 

Author
WJMZBMR
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-25 20:52:29, Gzip enabled