Little Elephant and Filling

Problem code: LUCKFILL

All submissions for this problem are available.

A Little Elephant from the Zoo of Lviv likes lucky strings, i.e., the strings that consist only of the lucky digits 4 and 7.

The Little Elephant has the string S such that each character in S is either the lucky digit (4 or 7) or the question mark ?. He can replace each question mark with one of the lucky digits in order to obtain the lucky string. He wants to know the number of different ways he can do this such that the resulting lucky string has no more than K different substrings. Help him and find this number. Note, that he need to replace all question marks.

Consider some example. From the string 47?4? we can obtain four lucky strings by replacing question marks with the lucky digits: 47444, 47447, 47744 and 47747. The corresponding numbers of different substrings are 11, 11, 12 and 11. For example, all different substrings of the string 47447 are 4, 7, 44, 47, 74, 447, 474, 744, 4744, 7447 and 47447.

Notes.

Let S be some lucky string. Then
  • |S| denotes the length of the string S;
  • S[i] (1 ≤ i ≤ |S|) denotes the ith character of S (the numeration of characters starts from 1);
  • The string T of the length M is called a substring of S if for some k from 0 to |S| - M we have
    T[1] = S[k + 1], T[2] = S[k + 2], ..., T[M] = S[k + M].

Input

The first line of the input file contains a single positive integer T, the number of test cases. T test cases follow. The first line of each test case contains two space separated integers N and K. The second line contains the string S of the length N.

Output

For each test case output a single line containing the answer for the corresponding test case.

Constraints

1 ≤ T ≤ 4747

1 ≤ N, K ≤ 50

For each string S from the input file we have that |S| = N and each character in S is either the lucky digit (4 or 7) or the question mark ?.

Example

Input:
2
2 2
??
3 7
?4?

Output:
2
4
Author: witua
Tester: anton_lunyov
Editorial http://discuss.codechef.com/problems/LUCKFILL
Date Added: 27-01-2012
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

@dawnavs 447 = S[3,5] and

anton_adm @ 20 May 2012 10:03 PM
@dawnavs 447 = S[3,5] and 47447 = S[1,5] is the string S itself.

@saroj T is the number of

anton_adm @ 20 May 2012 10:06 PM
@saroj T is the number of test cases. 1 <= T <= 4747 means that in each test file there will be no more than 4747 test cases.

@admin, would u mind

abhiuppar @ 20 May 2012 10:29 PM
@admin, would u mind explaining the second test case for ?4? with 3 as length of string and 7 as the possible number of substrings and please explain it completely ,Thanks.

@abhiuppar Note that each

anton_adm @ 20 May 2012 10:41 PM
@abhiuppar Note that each lucky string of length 3 has no more than 6 different substrings (S[1,1], S[1,2], S[1,3], S[2,2], S[2,3], S[3,3]). And we have k=7. Hence any replacement is good. There are 2*2=4 replacements in total (we have two "?")

this problem is still not in

saroj @ 21 May 2012 11:11 AM
this problem is still not in practice section.....

@saroj: The problem is there

admin @ 21 May 2012 03:59 PM

@saroj: The problem is there in practice section. Please check here: http://www.codechef.com/problems/LUCKFILL

@saroj: You can only submit

admin @ 21 May 2012 04:05 PM

@saroj: You can only submit for a problem in a contest untill it is running. After the end of he contest the problem will be moved to practice section. you can check them here: http://www.codechef.com/problems/medium.

SUCCESSFUL SUBMISSIONS


Fetching successful submissions