Problem: Consider the following game. There are k pairs of n cards with numbers from 1 to n written one by one. Shuffle these kn cards well to make piles of k cards and arrange them in a horizontal row. The i-th (k-card) pile from the left of the n piles created in this way is called "mountain i".

<image>


The game starts at mountain 1. Draw the top card of the pile (the drawn card is not returned to the original pile), and if the number written on that card is i, draw the top card of the pile i Pull. In this way, draw the top card of the pile numbered by the number written on the drawn card repeatedly, and if all the piles have no cards, it is successful. If there are still piles of cards left, but there are no more piles to draw next, it is a failure.

If it fails in the middle, it ends with a failure, or the remaining card pile is left as it is (the pile number is also kept as it is) and the game is restarted. When restarting the game, the first card to draw is from the leftmost pile of the remaining piles (the top card of that pile is the first card to be drawn). After resuming, proceed with the game in the same way as before resuming, and if there are no cards in all the piles, it is a success. It is a failure.

<image>


Such a game shall be restarted up to m times. However, m is 0 or 1. In other words, it either does not restart once or restarts only once. The initial placement of cards differs depending on how you shuffle before the game starts. Of course, depending on the initial placement of the card, it may succeed without resuming, it may resume and succeed, or it may resume and fail. Since it is shuffled enough, we assume that all initial arrangements appear with the same probability, and we want to find the probability p that the restart will succeed within m times. Express this probability p as a decimal number, and create a program that finds and outputs to the decimal place r. However, output so that the following conditions are met.

* If p × 10K becomes an integer when a sufficiently large positive integer K is taken, 0 continues from the middle of the decimal part, but that 0 should also be output. For example, if p = 3/8 = 0.375, then 0.37500 is output if r = 5, and 0.37 is output if r = 2. Similarly, when p = 1.0, for example, if r = 3, output 1.000.
* For example, 0.150000 ... can be expressed as a recurring decimal 0.1499999 ..., but in such a case, the former expression is used.



On the first line of the input file, the integers n, k, m, and r are written in this order with a blank as the delimiter. 1 ≤ n ≤ 10000, 1 ≤ k ≤ 100, m = 0 or m = 1, 1 ≤ r ≤ 10000.

Input example 1 | Input example 2 | Input example 3
--- | --- | ---
|
2 1 0 5 | 3 1 1 3 | 2 2 1 3 |
Output example 1 | Output example 2 | Output example 3
0.50000 | 0.833 | 1.000 |

input

The input consists of multiple datasets. Input ends when n, k, m, and r are all 0. The number of datasets does not exceed 5.

output

For each dataset, p is output on one line as specified.





Example

Input

2 1 0 5
3 1 1 3
2 2 1 3
0 0 0 0


Output

0.50000
0.833
1.000

Solution (in CPP):

Solution:
     #include <bits/stdc++.h>

//    #include <boost/multiprecision/cpp_int.hpp>
 #define int long long
 #define inf  1000000007
 #define pa pair<int,int>
 #define ll long long
 #define pal pair<double,double>
 #define ppap pair<pa,int>
//  #define PI 3.14159265358979323846
  #define paa pair<int,char>
  #define  mp make_pair
  #define  pb push_back
  #define EPS (1e-10)
                                          
    int dx[8]={0,-1,0,1,1,1,-1,-1};
    int dy[8]={1,0,-1,0,-1,1,1,-1};
                                            using namespace std;
                                   			class pa3{
                                            	public:
                                            	int x,y,z;
                                            	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                            	bool operator < (const pa3 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		 return z<p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                   				bool operator > (const pa3 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		 return z>p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa3 &p) const{
                                            		return x==p.x && y==p.y && z==p.z;
                                            	}
                                            		bool operator != (const pa3 &p) const{
                                            			return !( x==p.x && y==p.y && z==p.z);
                                            	}
                                            
                                            };
                                            
                                            class pa4{
                                            	public:
                                            	double x;
                                            	int y,z,w;
                                            	pa4(double x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                            	bool operator < (const pa4 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		if(z!=p.z)return z<p.z;
                                            		return w<p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator > (const pa4 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		if(z!=p.z)return z>p.z;
                                            		return w>p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa4 &p) const{
                                            		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                            	}
                                            		
                                            
                                            };
                                            class pa2{
                                            	public:
                                            	int x,y;
                                            	pa2(int x=0,int y=0):x(x),y(y) {}
                                            	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                            	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                            	bool operator < (const pa2 &p) const{
                                            		return y != p.y ? y<p.y: x<p.x;
                                            	}
                                            	bool operator > (const pa2 &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa2 &p) const{
                                            		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                            	}
                                            	bool operator != (const pa2 &p) const{
                                            		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                            	}
                                            		
                                            
                                            };
                                            
/*
                                            class Point{
                                            	public:
                                            	double x,y;
                                            	Point(double x=0,double y=0):x(x),y(y) {}
                                            	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
                                            	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
                                            	Point operator * (double a) {return Point(x*a,y*a);}
                                            	Point operator / (double a) {return Point(x/a,y/a);}
                                            	double absv() {return sqrt(norm());}
                                            	double norm() {return x*x+y*y;}
                                            	bool operator < (const Point &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const Point &p) const{
                                            		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
                                            	}
                                            };
                                            typedef Point Vector;
                                     #define pl pair<int,pas>
                                            struct Segment{
                                            Point p1,p2;
                                            };
                                             double dot(Vector a,Vector b){
                                            	return a.x*b.x+a.y*b.y;
                                            }
                                            double cross(Vector a,Vector b){
                                            	return a.x*b.y-a.y*b.x;
                                            }
                                        
                bool parareru(Point a,Point b,Point c,Point d){
                //	if(abs(cross(a-b,d-c))<EPS)cout<<"dd "<<cross(a-b,d-c)<<endl;
                	return abs(cross(a-b,d-c))<EPS;
                }
                double distance_ls_p(Point a, Point b, Point c) {
                  if ( dot(b-a, c-a) < EPS ) return (c-a).absv();
                  if ( dot(a-b, c-b) < EPS ) return (c-b).absv();
                  return abs(cross(b-a, c-a)) / (b-a).absv();
                }
                bool is_intersected_ls(Segment a,Segment b) {
                	if(a.p1==b.p1||a.p2==b.p1||a.p1==b.p2||a.p2==b.p2) return false;
                	if(parareru((a.p2),(a.p1),(a.p1),(b.p2))&&parareru((a.p2),(a.p1),(a.p1),(b.p1))){
                //		cout<<"sss"<<endl;
                		if(dot(a.p1-b.p1,a.p1-b.p2)<EPS) return true;
                		if(dot(a.p2-b.p1,a.p2-b.p2)<EPS) return true;
                		if(dot(a.p1-b.p1,a.p2-b.p1)<EPS) return true;
                		if(dot(a.p1-b.p2,a.p2-b.p2)<EPS) return true;
                		return false;
                	}
                  else return ( cross(a.p2-a.p1, b.p1-a.p1) * cross(a.p2-a.p1, b.p2-a.p1) < EPS ) && ( cross(b.p2-b.p1, a.p1-b.p1) * cross(b.p2-b.p1, a.p2-b.p1) < EPS );
                }
                 
                double segment_dis(Segment a,Segment b){
                	if(is_intersected_ls(a,b))return 0;
                	double r=distance_ls_p(a.p1, a.p2, b.p1);
                	r=min(r,distance_ls_p(a.p1, a.p2, b.p2));
                	r=min(r,distance_ls_p(b.p1, b.p2, a.p2));
                	r=min(r,distance_ls_p(b.p1, b.p2, a.p1));
                	return r;
                }
                Point intersection_ls(Segment a, Segment b) {
                  Point ba = b.p2-b.p1;
                  double d1 = abs(cross(ba, a.p1-b.p1));
                  double d2 = abs(cross(ba, a.p2-b.p1));
                  double t = d1 / (d1 + d2);
                 
                  return a.p1 + (a.p2-a.p1) * t;
                }
 */                
                                string itos( int i ) {
                                ostringstream s ;
                                s << i ;
                                return s.str() ;
                                }
                                 
                                int gcd(int v,int b){
                                	if(v>b) return gcd(b,v);
                                	if(v==b) return b;
                                	if(b%v==0) return v;
                                	return gcd(v,b%v);
                                }
                 
                                double distans(double x1,double y1,double x2,double y2){
                                	double rr=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
                                	return sqrt(rr);
                                	
                                }
                                int mod;
                                
                int pr[500010];
                int inv[500010];
                
                int beki(int wa,int rr,int warukazu){
                	if(rr==0) return 1%warukazu;
                	if(rr==1) return wa%warukazu;
                	if(rr%2==1) return (beki(wa,rr-1,warukazu)*wa)%warukazu;
                	int zx=beki(wa,rr/2,warukazu);
                	return (zx*zx)%warukazu;
                }
    double bekid(double w,int r){
    	if(r==0) return 1.0;
    	if(r==1) return w;
    	if(r%2) return bekid(w,r-1)*w;
    	double f=bekid(w,r/2);
    	return f*f;
    }
                
    			int comb(int nn,int rr){
    				int r=pr[nn]*inv[rr];
    				r%=mod;
    				r*=inv[nn-rr];
    				r%=mod;
    				return r;
    			}
                
                void gya(int ert){
                	pr[0]=1;
                	for(int i=1;i<ert;i++){
                		pr[i]=(pr[i-1]*i)%mod;
                	}
                	for(int i=0;i<ert;i++) inv[i]=beki(pr[i],mod-2,mod);
                	
                }
                
              //   cin.tie(0);
    		//	ios::sync_with_stdio(false);
    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                 //sort(ve.begin(),ve.end(),greater<int>());
                                         //----------------kokomade tenpure------------
                //vector<double> ans(100000000),ans2(100000000)
      


vector<int> ve(13001,0);

vector<int> tasu(vector<int> v1,vector<int> v2){
	int ku=0;
	for(int i=13000;i>0;i--){
		v1[i]+=v2[i]+ku;
		if(v1[i]>10)v1[i]-=10,ku=1;
		else ku=0;
	}
	v1[0]+=v2[0]+ku;
	return v1;
}

vector<int>waru(vector<int> v1,int d){
	int ku=0;
	vector<int> v2(13001,0);
	
	for(int i=0;i<=13000;i++){
		v2[i]=(ku*10+v1[i])/d;
		ku=(ku*10+v1[i])%d;
	}
	return v2;
}

vector<int> gyaku(int r){
	vector<int> v2(13001,0);
	v2[0]=1;
	return waru(v2,r);
}
  signed main(){
    	       cin.tie(0);
    			ios::sync_with_stdio(false);
while(1){
int n,k,m,r;
  	cin>>n>>k>>m>>r;
if(n==0)exit(0);
for(int i=0;i<13001;i++)ve[i]=0;
  	if(m==0){
  		
  		{
  			ve[0]=1;
  			ve=waru(ve,n);
  			cout<<ve[0]<<".";
  			for(int i=0;i<r;i++)cout<<ve[i+1];
  			cout<<endl;
  			continue;
  		}
  	}
  	
  	if(n<=2){
  		cout<<"1.";
  		for(int i=0;i<r;i++)cout<<"0";
  		cout<<endl;
  		continue;
  	}
  	
  	ve[0]=2;
  	for(int i=2;i<=n-1;i++){
  		vector<int> gya=gyaku(i);
  		ve=tasu(ve,gya);
  	}
  	ve=waru(ve,n);
  	
cout<<ve[0]<<".";
  			for(int i=0;i<r;i++)cout<<ve[i+1];
  			cout<<endl;
}
  	return 0;
    }