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:

  • R is "a" or "b".
  • R is of the form "(R1R2)" where R1 and R2 are regular expressions.
  • R is of the form "(R1|R2)" where R1 and R2 are regular expressions.
  • R is of the form "(R1*)" where R1 is a regular expression.

The set of strings recognised by R are as follows:

  • If R is "a", then the set of strings recognised = {a}
  • If R is "b", then the set of strings recognised = {b}
  • 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.
  • if R is of the form "(R1|R2)" then the set of strings recognised = union of the set of strings recognised by R1 and R2.
  • 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.

Example

Input:
3
((ab)|(ba)) 2
((a|b)*) 5
((a*)(b(a*))) 100

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, preceded and followed by any number of a's. Clearly, there are 100 strings of length 100 which have a single b in them.


Added by:Varun Jalan
Date:2012-01-09
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used for CodeSprint 2 - InterviewStreet Contest

hide comments
2017-09-14 09:22:27 [Rampage] Blue.Mary
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.
2016-03-25 10:27:59
Can anyone tell me if my submission's Time is anywhere near to time limit?
2015-03-06 11:16:10 Muhammad Yunus Bahari
reply from piotr: time limit changed.
thanks, finally AC ;)

Last edit: 2015-04-23 18:56:31
2012-12-15 12:29:43 Varun Jalan
Thanks :) Glad you enjoyed it.
2012-11-28 07:02:04 :D
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.

Hope we will see more from you in the coming years. Thank you for your work.

Last edit: 2013-01-10 20:18:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.