Problem C
Sultan's Chandelier
Input: Standard Input

Output: Standard Output

Once upon a time, there was a sultan, who built a huge palace for the one he loves. To show his affection, every thing from wall paints and paintings were chosen by him. Since our Sultan has a weird type of taste, the chandeliers in this palace looked like trees.

The chandeliers take a tree like structure. Each node of the tree has a colored light, and all it's children are placed equally spaced around it in clockwise direction. The child sub trees can be rotated around the node. Thus, One chandelier, can be rotated to look like another chandelier.

The sultan wants to know, given the basic structure of the chandelier, and the number of colored lights, how many different chandeliers can be created.

For example, for a tree like the following:

if the available colours are red and green, then only these chandeliers can be made:

Given the tree structure and the number of different lights, find the possible chandeliers that sultan can use.

The tree is represented recursively as the following:

<subtree> ::= '[' <tree list> ']' | '[ ]'

The <tree list> lists the sub trees rooted at the node. The tree drawn above can be represented using the following string:

[ [], [] ]

Input

Input will start with an integer T (T <= 4000), the number of test cases. Each of the following T lines each will contain a string containing only of '[', ',' and ']', describing the tree, and an integer C (C <= 100), the number of available colours for the lights in the chandelier. number of nodes in the tree will be <= 100.

Output

For each test case, output the case number, and the number of different chandelier sultan can have. Output the number % 1000000007.

Sample Input Output for Sample Input

[[],[],[]] 2

[] 2

[[],[]] 2

[[[],[]],[],[[],[]]] 2

[[[],[]],[],[],[[],[]]] 4

[[[],[]],[],[[],[]],[]] 4

Case #1: 8

Case #2: 2

Case #3: 6

Case #4: 144

Case #5: 102400

Case #6: 51520

Problemsetter: Manzurur Rahman Khan

Special Thanks to: Sabbir Yousuf Sanny