CTSTRING  Count Strings
A regular expression is used to describe a set of strings. For this problem the alphabet is limited to 'a' and 'b'. R is a regular expression if:
1) R is "a" or "b"
2) R is of the form "(R1R2)" where R1 and R2 are regular expressions
3) R is of the form "(R1R2)" where R1 and R2 are regular expressions
4) R is of the form "(R1*)" where R1 is a regular expression.
The set of strings recognised by R are as follows:
1) If R is "a", then the set of strings recognised = {a}
2) If R is "b", then the set of strings recognised = {b}
3) if R is of the form "(R1R2)" then the set of strings recognised = all strings which can be obtained by a concatenation of strings s1 and s2 where s1 is recognised by R1 and s2 by R2.
4) if R is of the form "(R1R2)" then the set of strings recognised = union of the set of strings recognised by R1 and R2.
5) If R is of the form "(R1*)" then the the strings recognised are the empty string and the concatenation of an arbitrary number of copies of any string recognised by R1.
Given a regular expression and an integer L, you need to count how many strings of length L are recognized by it.
Input:
The first line contains the number of test cases T. T test cases follow.
Each test case contains a regular expression R and an integer L.
Output:
Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007.
Constraints:
1 <= T <= 50
1 <= length(R) <= 100
1 <= L <= 10^9
You are guaranteed that R will conform to the definition provided above.
All inputs will be randomly generated.
Sample Input:
3
((ab)(ba)) 2
((ab)*) 5
((a*)(b(a*))) 100
Sample Output:
2
32
100
Explanation:
For the first case, the only strings recognized are "ab" and "ba".
For the second case, the regex recognizes any string containing only a's and b's. So the number of strings of length 5 recognized by it is 2^5 = 32.
For the third case, the regex recognizes any string having one b, preceeded and followed by any number of a's. Clearly, there are 100 strings of length 100 which have a single b in them.
hide comments
[Rampage] Blue.Mary:
20170914 09:22:27
Note that "all input is randomly generated". So you can assume that the numbers of ****** and ****** are relatively small. Then (A) you can use bitmask to simplify the code in step 1, (B) you can use ****** technique to get the answer without TLE. 

ash_hacker:
20160325 10:27:59
Can anyone tell me if my submission's Time is anywhere near to time limit? 

Muhammad Yunus Bahari:
20150306 11:16:10
reply from piotr: time limit changed.


Varun Jalan:
20121215 12:29:43
Thanks :) Glad you enjoyed it. 

:D:
20121128 07:02:04
Varun submitted many high quality problems over the years, but this must be his crowning achievement. Maybe it's easier with some knowledge on actual implementations of RE, but coming to it blind, is a great learning experience. Very deep problem.

Added by:  Varun Jalan 
Date:  20120109 
Time limit:  0.100s0.150s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem used for CodeSprint 2  InterviewStreet Contest 