

DiceTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1658 Accepted Submission(s): 936 Special Judge Problem Description You have a dice with m faces, each face contains a distinct number. We assume when we tossing the dice, each face will occur randomly and uniformly. Now you have T query to answer, each query has one of the following form: 0 m n: ask for the expected number of tosses until the last n times results are all same. 1 m n: ask for the expected number of tosses until the last n consecutive results are pairwise different. Input The first line contains a number T.(1¡ÜT¡Ü100) The next T line each line contains a query as we mentioned above. (1¡Üm,n¡Ü10^{6}) For second kind query, we guarantee n¡Üm. And in order to avoid potential precision issue, we guarantee the result for our query will not exceeding 10^{9} in this problem. Output For each query, output the corresponding result. The answer will be considered correct if the absolute or relative error doesn't exceed 10^{6}. Sample Input
Sample Output
Source  
