Little Elephant and CNSes

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 N favorite strings S_{1}, S_{2}, ..., S_{N} and the favorite number K. Each character in S_{i} (1 ≤ i ≤ N) is either the lucky digit (4 or 7) or the question mark ?.
Consider some nondecreasing lucky string S. In other words, S has one of the following forms: 444...444, 777...777, 444...444777...777. The string S is called a CNS (plural form is CNSes) if we can replace some (possibly zero) number of question marks with the lucky digits in each of the string S_{1}, S_{2}, ..., S_{N} in a such way that the total number of replacements for all strings does not exceed K and S is a subsequence of each of the strings derived after the replacement.
The Little Elephant wants to know the total number of all different nonempty CNSes. Help him to find this number.
Notes.
Let S be some string (possibly not lucky). Then
 S denotes the length of the string S;
 S[i] (1 ≤ i ≤ S) denotes the i^{th} character of S (the numeration of characters starts from 1);
The string T is called a subsequence of the string S if T can be derived from S by deleting some (possibly zero) number of characters without changing the order of the remaining characters. For example, T = 474 is a subsequence of S = 74477747?? since after deleting characters at positions 1, 2, 5, 6, 8, 9, 10 from S we obtain T. Note that, the empty string and the string S itself are always the subsequences of S.
Input
The first line of the input file contains two space separated integers N and K, the number of strings in the set and the favorite number of the Little Elephant. Each of the following N lines contains one favorite string of the Little Elephant. Namely, i^{th} line among these N lines contains the string S_{i}.
Output
For each test case output a single line containing the answer for this test case.
Constraints
1 ≤ N ≤ 7474
0 ≤ K ≤ 10^{9}
S_{i} is nonempty for 1 ≤ i ≤ N.
S_{1} + S_{2} + ... + S_{N} ≤ 100000. In other words, the total length of all N strings does not exceed 100000.
Each character in S_{i} (1 ≤ i ≤ N) is either the lucky digit (4 or 7) or the question mark ?.
Example
Input: 3 2 4447 47???74 4?77? Output: 5
Explanation
For the sample input all different CNSes are 4, 7, 44, 47 and 447. Note, that 444 is not a CNS since it requires at least 3 replacements of the question marks.
Author:  witua 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/LUCKYCOM 
Tags  cook22, medium, witua 
Date Added:  1032012 
Time Limit:  0.3  0.386276 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 