import java.math.BigInteger;
import java.util.LinkedHashMap;

class CountStrings2 {

	// cache. key: N:M
	private LinkedHashMap<String, BigInteger> sNM = new LinkedHashMap<String, BigInteger>();
	private final int P;

	public CountStrings2(int P, int N, int M) {
		this.P = P;
		BigInteger S = computeS(N, M);
		System.out.println("P=" + P + " N=" + N + " M=" + M + " S=" + S);
		//outputCaches();
		computeAsympt(N,M);
	}

	private BigInteger computeS(int N, int M) {
		String k = N + ":" + M;
		if (!sNM.containsKey(k)) {
			BigInteger b = BigInteger.ZERO;
			if (N < M) {
				b = BigInteger.valueOf(P).pow(N);
			} else {
				for (int i= 1; i < M; i++) {
					b = b.add(computeS(N-i, M));
				}
				b = b.multiply(BigInteger.valueOf(P-1));
			}
			sNM.put(k, b);
		}

		return sNM.get(k);
	}

	public void outputCaches() {
		System.out.println("============== SNM ====  (P=" + P + ")");
		for (String k : sNM.keySet()) {
			System.out.println("SNML " + k + "=" + sNM.get(k));
		}
	}

	public void computeAsympt(int N, int M) { // asympotic approximation 
		double theta = 1.0 / P;
		double probasympt =  Math.pow(1 - Math.pow(theta, M - 1),N * (1 - theta));
		BigInteger S = computeS(N, M);
		BigInteger cc = BigInteger.valueOf(P).pow(N).multiply(BigInteger.valueOf(1000000)).divide(S);
		double probexact = 1000000.0/cc.doubleValue();
		System.out.printf("prob:%.4f asymptotic:%.4f\n" ,probexact, probasympt);
	}

	public static void main(String[] args) {
		new CountStrings2(4, 50, 5);

	}
}