DiceTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1658 Accepted Submission(s): 936
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.
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¡Ü106) 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 109 in this problem.
For each query, output the corresponding result. The answer will be considered correct if the absolute or relative error doesn't exceed 10-6.