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 > ::= ‘[’< treelist >‘]’ | ‘[]’ < treelist > ::= < subtree > | < subtree >‘,’< treelist >
2/2 The < treelist > 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. The 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 6 [[],[],[]] 2 [] 2 [[],[]] 2 [[[],[]],[],[[],[]]] 2 [[[],[]],[],[],[[],[]]] 4 [[[],[]],[],[[],[]],[]] 4 Sample Output Case #1: 8 Case #2: 2 Case #3: 6 Case #4: 144 Case #5: 102400 Case #6: 51520