Jack and Jill like to play with coins. They are interested in the patterns generated after n times flip of a coin. As you know, in case of a fair coin if you flip the coin 3 times, you can get either of the following patterns. HHH THH HHT THT HTH TTH HTT TTT The numbers of different patterns increase exponentially with the increase of number of flips. Jack and Jill categorizes all the patterns considering the sub-patterns they have H HHH, HHT, HTH, HTT, THH, THT, TTH, TTT HH HHH, HHT, THH HT HHT, HTH, HTT, THT TTH TTH It is not always possible to examine each pattern. So, some intelligent technique is necessary to do such task. The problem you need solve for Jack and Jill is to find the probability of getting patterns which will not contain any of the previously defined sub-patterns. Input Each test case starts with a positive integer N (1 ≤ N ≤ 50) which means the number of flips and K (0 ≤ K ≤ 50) indicating the number of sub-patterns. Nest K lines will contain the sub-patterns which will be a sequence of H and T. All sub-patterns have same length and it will be at most 10. Input is terminated by N = K = 0. This case should not be processed. There can be at most 100 test cases. Output Output of each test case should consist of a line starting with ‘Case #:’ where ‘#’ is the test case number. It should be followed by the probability of getting patterns which will not contain any of the given K sub-patterns. If the probability is non-zero, then print it in the form of ‘a/b’ where a, b are properly reduced. If the probability is zero, then print ‘0’ simply. Sample Input 31 HH 31 HT 32 T H 00
2/2 Sample Output Case 1: 5/8 Case 2: 1/2 Case 3: 0