
ZOJ Problem Set  2709
Many lotteries now publish ads proclaiming that they have a superprize in each ticket. The idea is the following. The ticket has n windows, each of which contains some letter. Initially all windows are covered by the opaque substance. A person who buys the ticket removes the covering substance from m windows and if the letters revealed can be combined to form the winning mletter word, the ticket owner wins the superprize. The advertised features are the following: each ticket can win, and the only letters that are hidden in the windows are the letters from the winning word. Assuming that the person uncovers m randomly chosen windows, you have to find the probability of winning a superprize. Of course, the winning probability depends on the exact multiset of the letters in the windows. For example, if the winning word is “WOW” and there are four windows, the letters used may be:
Input There are mutiple cases in the input file. The first line of each case contains n (1 <= n <= 60 ). The second line contains the winning word. It contains only capital letters of the English alphabet, its length does not exceed n. There is an empty line after each case. Output On the first line of the output file print the maximal possible probability of winning, as an irreducible fraction. On the second line print the minimal possible probability of winning in the same form. There should be am empty line after each case.Sample Input 4 WOW 7 VICTORY 60 ABRACADABRA Sample Output 3/4 1/2 1/1 1/1 635250/29290609 1/6854002506 Source: Andrew Stankevich's Contest #10 