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.