( ext{Part.1})
令(f_i)为结束时序列长度为(i)的概率，其PGF为(F(x))。
令(g_i)为序列长度达到(i)且尚未结束的概率，其OGF为(G(x))。
分析可得：
[egin{aligned}
F(x)+G(x)&=xG(x)+1\
(frac xm)^{n-1}G(x)&=sumlimits_{i=1}^n(frac xm)^{n-i}F(x)
end{aligned}
]
解得(ans=F'(1)=sumlimits_{i=0}^{n-1}m^i)。
( ext{Part.2})
令(f_i)为结束时序列长度为(i)的概率，其PGF为(F(x))。
令(g_i)为序列长度达到(i)且尚未结束的概率，其OGF为(G(x))。
分析可得：
[egin{aligned}
F(x)+G(x)&=xG(x)+1\
(frac xm)^nfrac{m!}{(m-n)!}G(x)&=sumlimits_{i=1}^n(frac xm)^{n-i}frac{(m-i)!}{(m-n)!}F(x)
end{aligned}
]
解得(ans=F'(1)=sumlimits_{i=1}^nfrac{(m-i)!}{m!}m^i)。
#include<cmath>
#include<iomanip>
#include<iostream>
using namespace std;
long double cal(int n,int m){long double s=0,t=1;for(int i=1;i<=n;++i)t=t*m/(m-i+1),s+=t;return s;}
int main()
{
int t,o,n,m;
for(cin>>t;t;--t)
{
cin>>o>>m>>n;
if(!o) cout<<fixed<<setprecision(10)<<(m==1? n:(pow(m,n)-1)/(m-1))<<endl;
else cout<<fixed<<setprecision(10)<<cal(n,m)<<endl;
}
}