N = 2
M = 1
K = 3
maxValue = M*K
 
count = [0] * (maxValue+1)
prev = [0] * (maxValue+1)
 
count[0] = 1 # empty set
 
for i in range(K):
	# move count to prev
	for index in range(maxValue+1):
		prev[index] = count[index]
		count[index] = 0
 
	rollingSum = 0
 
	# calculate new counts
	for Sum in range(maxValue+1):
		rollingSum += prev[Sum]
		if (Sum > M):
			rollingSum -= prev[Sum - (M + 1)]
		count[Sum] = rollingSum
 
 
# add all counts of sets whose sum is >= N
ans = sum(count[N:]) / pow(M+1,K)
print(ans)
 

TiA9IDIKTSA9IDEKSyA9IDMKbWF4VmFsdWUgPSBNKksKCmNvdW50ID0gWzBdICogKG1heFZhbHVlKzEpCnByZXYgPSBbMF0gKiAobWF4VmFsdWUrMSkKCmNvdW50WzBdID0gMSAjIGVtcHR5IHNldAoKZm9yIGkgaW4gcmFuZ2UoSyk6CgkjIG1vdmUgY291bnQgdG8gcHJldgoJZm9yIGluZGV4IGluIHJhbmdlKG1heFZhbHVlKzEpOgoJCXByZXZbaW5kZXhdID0gY291bnRbaW5kZXhdCgkJY291bnRbaW5kZXhdID0gMAoJCglyb2xsaW5nU3VtID0gMAoJCgkjIGNhbGN1bGF0ZSBuZXcgY291bnRzCglmb3IgU3VtIGluIHJhbmdlKG1heFZhbHVlKzEpOgoJCXJvbGxpbmdTdW0gKz0gcHJldltTdW1dCgkJaWYgKFN1bSA+IE0pOgoJCQlyb2xsaW5nU3VtIC09IHByZXZbU3VtIC0gKE0gKyAxKV0KCQljb3VudFtTdW1dID0gcm9sbGluZ1N1bQoJCQkKCiMgYWRkIGFsbCBjb3VudHMgb2Ygc2V0cyB3aG9zZSBzdW0gaXMgPj0gTgphbnMgPSBzdW0oY291bnRbTjpdKSAvIHBvdyhNKzEsSykKcHJpbnQoYW5zKQo=