The itertools module standardizes a core set of fast, memory efficient tools that are useful by themselves or in combination. Together, they form an iterator algebra making it possible to construct specialized tools succinctly and efficiently in pure Python. 

To read more about the functions in this module, check out their documentation here. 

You are given a list of $N$ lowercase English letters. For a given integer $\mbox{K}$, you can select any $\mbox{K}$ indices (assume $\mbox{I}$-based indexing) with a uniform probability from the list.  

Find the probability that at least one of the $\mbox{K}$ indices selected will contain the letter: '$\boldsymbol{\alpha}$'.  

Input Format

The input consists of three lines. The first line contains the integer $N$, denoting the length of the list. The next line consists of $N$ space-separated lowercase English letters, denoting the elements of the list. 

The third and the last line of input contains the integer $\mbox{K}$, denoting the number of
indices to be selected. 

Output Format

Output a single line consisting of the probability that at least one of the $\mbox{K}$ indices selected contains the letter:'$\boldsymbol{\alpha}$'. 

Note: The answer must be correct up to 3 decimal places. 

Constraints

$1\leq N\leq10$

$1\leq K\leq N$

All the letters in the list are lowercase English letters.

Sample Input

4 
a a c d
2

Sample Output

0.8333

Explanation

All possible unordered tuples of length $2$ comprising of indices from $\mbox{I}$ to $\begin{array}{c}A\end{array}$ are:

$(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$ 

Out of these $\boldsymbol{6}$ combinations, $5$ of them contain either index $\mbox{I}$ or index $2$ which are the indices that contain the letter '$\boldsymbol{\alpha}$'. 

Hence, the answer is $\frac{5}{6}$.

Source: hackerrank | Difficulty: MEDIUM


Solutions:
import itertools
import sys
N = int(sys.stdin.readline())
A = sys.stdin.readline().strip().split()
K = int(sys.stdin.readline())
(a, b) = (0, 0)
for x in itertools.permutations(A, K):
	a += 'a' in x
	b += 1
print(a / b)


import math

def ncr(n, r):
	f = math.factorial
	return f(n) / f(r) / f(n - r)
n = int(input())
a = list(map(str, input().split()))
k = int(input())
counta = 0
for i in range(n):
	if str(a[i]) == 'a':
		counta = counta + 1
up = ncr(n, k)
if n - counta < k:
	print('1')
else:
	low = ncr(n - counta, k)
	x = (up - low) / up
	print(float('{0:.3f}'.format(x)))


def calc(thing, combos, curr, i, turns):
	curr.append(thing[i])
	if len(curr) >= turns or i >= len(thing):
		if len(curr) >= turns:
			combos.append(curr)
		return
	for j in range(i + 1, len(thing)):
		calc(thing, combos, list(curr), j, turns)
n = int(input())
thing = input().replace(' ', '')
k = int(input())
total = []
for i in range(n):
	calc(thing, total, [], i, k)
count = 0
for i in range(len(total)):
	found = False
	for j in range(len(total[i])):
		if total[i][j] == 'a':
			found = True
	if found:
		count += 1
print(round(float(count) / float(len(total)), 3))


def fac(x):
	factorial = 1
	for i in range(x):
		factorial *= x - i
	return factorial
N = int(input())
a = [str(i) for i in input().split()]
K = int(input())
kol = 0
all_kol = 0
for i in range(len(a)):
	if a[i] == 'a':
		kol += 1
all_kol = int(fac(N) / fac(N - K) / fac(K))
without_a = int(fac(N - kol) / fac(K) / fac(N - kol - K))
if N != 1:
	if all_kol - without_a < all_kol:
		print((all_kol - without_a) / all_kol)
	else:
		print(1)
else:
	print(kol)


from itertools import combinations
n = int(input())
l = list(input().split())
k = int(input())
counter = 0
count_a = 0
l1 = [item for item in combinations(l, k)]
l2 = [item for item in combinations(l, k) if 'a' in item]
print(len(l2) / len(l1))


from itertools import combinations
n = int(input())
letters = input().split()
k = int(input())
x = list(combinations(letters, k))
a_count = 0
for t in x:
	for c in t:
		if c == 'a':
			a_count += 1
			break
print(a_count / len(x))


t = int(input())
l = input().split()
count = l.count('a')
n = int(input())
p = 1.0
for i in range(n):
	p *= (t - count - i) / (t - i)
print(1 - p)


import itertools
n = int(input())
string = ''.join(input().split())
k = int(input())
(a, b) = (0, 0)
for i in itertools.combinations(string, k):
	b += 1
	if 'a' in i:
		a += 1
print(a / b)


from math import factorial
n = int(input())
num_a = sum((1 for x in input().split() if x == 'a'))
k = int(input())
div = factorial(n) / (factorial(k) * factorial(n - k))
if n - num_a == 0 or n - num_a - k < 0:
	print(1)
else:
	print((div - factorial(n - num_a) / (factorial(k) * factorial(n - num_a - k))) / div)


from itertools import combinations
n = int(input())
L = list(input().split(' '))
r = int(input())
C = combinations(L, r)
count = 0
total = 0
for i in C:
	total = total + 1
	if 'a' in i:
		count = count + 1
print(count / total)


N = int(input())
C = input().split(' ').count('a')
K = int(input())
num_fails = N - C
prob = 1.0
if num_fails >= K:
	for i in range(K):
		prob *= (num_fails - i) / (N - i)
	prob = 1 - prob
print('{0:.3f}'.format(prob))


import itertools
n = int(input())
s = input().replace(' ', '')
k = int(input())
combinations = list(itertools.combinations(s, k))
print(sum(['a' in combination for combination in combinations]) / len(combinations))


n = int(input())
A = [i for i in input().strip().split()]
k = int(input())
(c, p) = (n - A.count('a'), 1)
for i in range(k):
	p *= (c - i) / (n - i)
print(1 - p)


from itertools import combinations
n = int(input())
s = list(map(str, input().split()))
k = int(input())
cmb = combinations(range(1, n + 1), k)

def a_indices():
	return [i + 1 for (i, x) in enumerate(s) if x == 'a']
i = 0
a = 0
for c in cmb:
	a += 1
	inter = set(c) & set(a_indices())
	if inter != set():
		i += 1
print(i / a)


import itertools
k = int(input())
n = list(input().split())
a = int(input())
t = 0
f = 0
for k in itertools.combinations(n, a):
	if 'a' in k:
		f = f + 1
	t = t + 1
print(float(f / t))


from itertools import combinations as C
(n, l, k) = (int(input()), input().split(), int(input()))
res = ['a' in i for i in C(l, k)]
print(res.count(True) / len(res))


from itertools import combinations
n = int(input())
letters = input().split()
k = int(input())
count = 0
comb = list(combinations(letters, k))
for c in comb:
	if 'a' in c:
		count += 1
print(count / len(comb))


from math import factorial

def C(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r))
N = int(input())
p = input().split()
K = int(input())
if K == 0:
	print(1)
elif N == K:
	if 'a' in p:
		print(1)
	else:
		print(0)
else:
	x = C(N - p.count('a'), K)
	y = C(N, K)
	if x < 0 or y <= 0:
		print(0)
	else:
		print(1 - x / y)


n = int(input())
s = input().split(' ')
k = int(input())
c = []
for i in range(0, n + 1):
	a = [1]
	for j in range(1, i + 1):
		a.append(c[i - 1][j - 1] + c[i - 1][j])
	a.append(0)
	c.append(a)
cnt = 0
for char in s:
	if char != 'a':
		cnt += 1
a = 0
if k <= cnt:
	a = c[cnt][k]
ans = float(c[n][k] - a) / float(c[n][k])
print(ans)


import sys
n = int(sys.stdin.readline())
letters = sys.stdin.readline()
a = list(letters).count('a')
k = int(sys.stdin.readline())
p = 1
for i in range(n, n - k, -1):
	p = p * (1 - float(a) / i)
print(1 - p)


from itertools import combinations
n = int(input())
l = input().split()
ind = int(input())
count = 0
c = list(combinations(l, ind))
for i in c:
	if 'a' in i:
		count += 1
print(count / len(c))


from collections import Counter
n = int(input())
j = Counter(list(input().split()))
aas = j['a']
K = int(input())
total = 1
for i in range(1, K + 1):
	total *= (n - aas) / n
	n -= 1
print(1 - total)


from math import factorial

def binomCoef(n, k):
	return factorial(n) / (factorial(k) * factorial(n - k))

def hypergeomPMF(k, N, K, n):
	A = binomCoef(K, k)
	B = binomCoef(N - K, n - k)
	C = binomCoef(N, n)
	return A * B / C
popSize = int(input())
S = str(input()).split()
draws = int(input())
num_of_As = S.count('a')
if num_of_As == 0:
	print('0.0000')
elif popSize == num_of_As:
	print('1.0000')
elif popSize == draws:
	print('1.0000')
else:
	print(round(1 - hypergeomPMF(0, popSize, num_of_As, draws), 4))


import itertools
N = int(input())
inputList = input().split()
K = int(input())
totCount = 0
reqCount = 0
for subset in itertools.combinations(inputList, K):
	totCount += 1
	if 'a' in subset:
		reqCount += 1
print(reqCount / totCount)


from functools import reduce

def f(n):
	if n == 0:
		return 1
	return reduce(lambda x, y: x * y, range(1, n + 1))

def C(n, k):
	if k > n:
		return 0
	return f(n) // f(k) // f(n - k)
n = int(input())
a = input().split()
k = int(input())
m = a.count('a')
print(1 - C(n - m, k) / C(n, k))


from itertools import combinations
N = int(input())
letters = input().split()
K = int(input())
comb = list(combinations(letters, K))
print(sum(['a' in x for x in comb]) / len(comb))


from math import factorial
ncr = lambda n, r: factorial(n) / (factorial(r) * factorial(n - r))
N = int(input())
letters = input().split(' ')
K = int(input())
not_a = len(letters) - letters.count('a')
if K > N or N == 0:
	print(0)
elif K > not_a:
	print(1)
else:
	print(1 - ncr(not_a, K) / ncr(N, K))


import math
try:

	def nCr(n, r):
		f = math.factorial
		return f(n) / (f(r) * f(n - r))
	input()
	L = [x for x in input().split()]
	k = int(input())
	d = {}
	a_count = 0
	for c in L:
		if c == 'a':
			a_count += 1
	print(1 - nCr(len(L) - a_count, k) / nCr(len(L), k))
except:
	print(1)


from itertools import combinations
n = int(input())
i = input().split()
k = int(input())
l = combinations(i, k)
cntns = 0
cnt = 0
for ls in l:
	cnt += 1
	if 'a' in ls:
		cntns += 1
print(cntns / cnt)


from itertools import combinations
N = int(input())
letters = input().split()
K = int(input())
(count, total) = (0, 0)
for group in combinations(letters, K):
	total += 1
	has_a = False
	for c in group:
		if c == 'a':
			has_a = True
	if has_a == True:
		count += 1
print(count / total)


import itertools
input_max = input()
input_list = input().split()
input_size = int(input())
combinations = [e for e in itertools.combinations(input_list, input_size)]
count = 0
for e in combinations:
	if 'a' in e:
		count += 1
print(format(count / len(combinations), '.4f'))


from itertools import combinations
from itertools import permutations
n = int(input().strip())
lst = list(input().strip().split())
k = int(input().strip())
cnt = lst.count('a')
cmb1 = list(combinations(lst, k))
cmb2 = list(combinations(lst[cnt:], k))
print((len(cmb1) - len(cmb2)) / len(cmb1))


import itertools as it
input()
l = input().split()
n = int(input())
(total, containing) = (0, 0)
for t in it.combinations(range(1, len(l) + 1), n):
	total += 1
	for i in t:
		if l[i - 1] == 'a':
			containing += 1
			break
print(containing / total)


def comb(n, k):
	val = n
	tg = n - k
	while n - 1 > tg:
		n = n - 1
		val = val * n
	div = 1
	while k > 1:
		div = div * k
		k = k - 1
	return val / div
n = int(input())
a = input().split()
k = int(input())
cnt = 0
for x in a:
	if x == 'a':
		cnt = cnt + 1
tot = comb(n, k)
non = comb(n - cnt, k)
ret = float(tot - non) / tot
print(round(ret, 3))


import itertools
N = int(input())
letters = input().split()
K = int(input())
aCount = sum((x == 'a' for x in letters))
ret = 0
tot = 0
for c in itertools.combinations(letters, K):
	if 'a' in c:
		ret += 1
	tot += 1
print(ret / tot)


import sys

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res *= i
	return res

def prob(data, k):
	count = len([c for c in data if c == 'a'])
	if len(data) - k < count:
		return 1.0
	n = len(data)
	return 1.0 - fact(n - count) * fact(n - k) / fact(n - count - k) / fact(n)

def run():
	sys.stdin.readline()
	data = sys.stdin.readline().split()
	k = int(sys.stdin.readline())
	print(prob(data, k))
run()


from itertools import combinations
n = int(input())
lista = list(input().split())
k = int(input())
omega = list(combinations(lista, k))
A = [1 for el in omega if 'a' in el]
print(round(sum(A) / len(omega), 3))


from itertools import combinations
n = int(input())
ar = input().split()
k = int(input())
comb_list = list(combinations(ar, k))
a_list = [e for e in comb_list if 'a' in e]
print(len(a_list) / len(comb_list))


import itertools
N = int(input())
letters = ''.join(input().strip().split())
K = int(input())
combinations = list(itertools.combinations(letters, K))
number_of_combinations = len(combinations)
number_of_combinations_with_a = len([x for x in combinations if 'a' in x])
probability = round(number_of_combinations_with_a / number_of_combinations, 3)
print(probability)


from itertools import combinations
from functools import reduce
from operator import add
input()
res = reduce(add, input().split())
K = int(input())
t = list(combinations(res, K))
print(sum((1 for v in t if 'a' in v)) / len(t))


from itertools import combinations

def inTuple(c, tup):
	if c in tup:
		return True
	else:
		return False
n = int(input())
letters = input().split()
k = int(input())
p = list(combinations(letters, k))
s = len(list(filter(lambda x: inTuple('a', x), p)))
print(s / len(p))


from itertools import combinations
l = (input(), input().split())[1]
k = int(input())
a = la = 0
for c in combinations(l, k):
	la += 1
	if 'a' in c:
		a += 1
print(a / la)


def probability(n, k, array):

	def comb(n, k):
		if k < 0 or k > n or n < 0:
			return 0
		if k == 0 or k == n or n == 0:
			return 1
		upper = n
		lower = 1
		for i in range(2, k + 1):
			upper *= n + 1 - i
			lower *= i
		return upper // lower
	total = float(comb(n, k))
	count = sum([x == 'a' for x in array])
	sub = 0
	for i in range(1, count + 1):
		sub += comb(n - i, k - 1)
	return float(sub) / total
n = int(input())
array = [x for x in input().strip().split(' ')]
k = int(input())
p = probability(n, k, array)
s = '{}'.format(p)
print(s)


from itertools import combinations
n = int(input().rstrip())
l = input().rstrip().split()
k = int(input().rstrip())
c = 0
for i in combinations(l, k):
	if 'a' in i:
		c += 1
print('{}'.format(c / len(list(combinations(l, k)))))


def question6():
	from itertools import combinations
	number = int(input())
	letters = str(input())
	combination = int(input())
	list_letters = []
	indexs_a = []
	a_index = 0
	for ch in letters.split(' '):
		list_letters.append(ch)
		if ch is 'a':
			indexs_a.append(a_index)
		a_index += 1
	list_indexes = []
	for i in range(number):
		list_indexes.append(i)
	list_combination = list(combinations(list_indexes, combination))
	count = 0
	for i in list_combination:
		for j in indexs_a:
			if j in i:
				count += 1
				break
	print(count / len(list_combination))
question6()


import itertools
N = int(input())
L = input().split()
K = int(input())
W = ['a' in c for c in itertools.combinations(L, K)]
r = 1.0 * W.count(True) / len(W)
print(r)


from itertools import combinations
input()
symbols = input().split()
count = int(input())
combs = list(combinations(symbols, count))
print(sum((any((s == 'a' for s in c)) for c in combs)) / len(combs))


import math

def acount(s):
	count = 0
	for c in s:
		if c == 'a':
			count += 1
	return count

def aprob(n, l, k):
	c = acount(l)
	np = (n - c) / n
	for i in range(1, k):
		a = n - i - c
		np = np * (a / (n - i))
	return 1 - np
N = int(input())
l = input()
K = int(input())
print(aprob(N, l, K))


from itertools import combinations
N = int(input())
S = input().split()
K = int(input())
c = combinations(S, K)
total = 0
a = 0
for x in c:
	total += 1
	if 'a' in x:
		a += 1
print(a / total)


from functools import reduce
from operator import mul

def comb(m, p):
	return reduce(mul, [m - j for j in range(p)], 1) // reduce(mul, list(range(1, p + 1)), 1)
n = int(input())
ls = input().split()
k = int(input())
na = ls.count('a')
ma = n - na
if n == na:
	print(1)
elif 0 == na or n < na:
	print(0)
else:
	tot = comb(n, k)
	za = comb(ma, k)
	print((tot - za) / tot)


from math import factorial
length = int(input())
this = input()
count = this.count('a')
k = int(input())
ans = 1
if k > length - count:
	print(1)
else:
	ans = factorial(length - count) * factorial(length - k) / (factorial(length - count - k) * factorial(length))
	print(1 - ans)


from itertools import combinations
N = int(input())
A = input().split()
K = int(input())
C = list(combinations(A, K))
Ca = [t for t in C if 'a' in t]
p = len(Ca) / len(C)
print('%.3f' % p)


from itertools import groupby
import math
N = int(input())
List = [[k, len(list(g))] for (k, g) in groupby(sorted(input().strip().split()))]
K = int(input())
if List[0][0] == 'a':
	a_count = List[0][1]
else:
	a_count = 0
propability = 1.0
for i in range(K):
	propability *= (N - a_count) / N
	N -= 1
print(1 - propability)


import itertools
n = int(input())
lst = [i for i in input().split()]
k = int(input())
b = list(itertools.combinations(lst, k))
total = len([1 for i in b if 'a' in i])
print('%.3f' % (total / len(b)))


import sys
from itertools import combinations

def main():
	f = sys.stdin
	N = int(f.readline())
	letters = [l for l in f.readline().split()]
	K = int(f.readline())
	(x, y) = (0, 0)
	for i in combinations(letters, K):
		x += 'a' in i
		y += 1
	print(x / y)
main()


def fact(n):
	f = 1
	while n > 0:
		f *= n
		n -= 1
	return f
N = int(input())
Na = 0
for c in input().split():
	if c == 'a':
		Na += 1
K = int(input())
print(1 - (fact(N - Na) * fact(N - K) / fact(N) / fact(N - Na - K) if K <= N - Na else 0))


from itertools import combinations
n = int(input())
s = input().split()
k = int(input())
x = list(combinations(s, k))
a = 0
for c in x:
	if 'a' in c:
		a += 1
print(round(a / len(x), 12))


from math import *
import time
import random
import sys

def nCr(n, r):
	return factorial(n) / (factorial(r) * factorial(n - r))
n = int(input())
s = input().split(' ')
count = 0
for i in s:
	if i == 'a':
		count += 1
k = int(input())
if count > n:
	sys.exit(0)
ans = 0
if n - count < k:
	ans = 1
else:
	ans = 1 - nCr(n - count, k) / nCr(n, k)
print(ans)


from itertools import combinations
n = int(input())
l = input().split()
k = int(input())
(total, ans) = (0, 0)
for cmb in combinations(l, k):
	total += 1
	if 'a' in cmb:
		ans += 1
print('{:.3f}'.format(ans / total))


import math

def ncr(n, r):
	return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
n = int(input())
penis = input().split()
k = int(input())
if n - penis.count('a') >= k:
	result = 1 - ncr(n - penis.count('a'), k) / ncr(n, k)
else:
	result = 1
print(result)


n = int(input())
a = []
a = input().split()
k = int(input())
counta = 0
for i in range(0, n):
	if a[i] == 'a':
		counta = counta + 1
r = 1
s = 1
for i in range(n - k - counta + 1, n - k + 1):
	r = r * i
for i in range(n - counta + 1, n + 1):
	s = s * i
print(1 - r / s)


import itertools
n = int(input())
li = list(input().split())
k = int(input())
my_list = list(itertools.combinations(li, k))
count = 0
for item in my_list:
	if 'a' in item:
		count += 1
result = count / len(my_list)
print(result)


from itertools import combinations

def main():
	n = int(input())
	l = input().split()
	k = int(input())
	ans = 0
	s = 0
	for i in combinations(l, k):
		if 'a' in i:
			ans += 1
		s += 1
	print(ans / s)
main()


import math
cnp = lambda n, p: math.factorial(n) // (math.factorial(p) * math.factorial(n - p))
n = int(input())
l = input().split()
k = int(input())
t = cnp(n, k)
nb = l.count('a')
v = 0
for i in range(1, nb + 1):
	if k - 1 > n - i:
		break
	v += cnp(n - i, k - 1)
p = v / t
print(p)


from itertools import combinations
__author__ = 'namii'
N = 4
stringi = 'a a c d'
K = 2
(N, stringi, K) = (input(), input(), input())
L = list(stringi.split())
combs = combinations(L, int(K))
(count, matches) = (0, 0)
for combination in combs:
	count += 1
	if 'a' in combination:
		matches += 1
print('{:.4f}'.format(matches / count))


from functools import reduce
from operator import mul

def comb(m, p):
	return reduce(mul, [m - j for j in range(p)], 1) // reduce(mul, list(range(1, p + 1)), 1)
n = int(input())
ls = input()
k = int(input())
na = ls.count('a')
if k < na:
	(na, k) = (k, na)
(tot, ta, m) = (comb(n, k), 0, n - na)
for i in range(1, na + 1):
	ta += comb(m, k - i) * comb(na, i)
print(ta / tot)


import itertools

def main():
	N = int(input())
	letters = input().split()
	K = int(input())
	combinations = list(itertools.combinations(letters, K))
	print(len(list(filter(lambda combination: 'a' in combination, combinations))) / len(combinations))
main()


from math import factorial as f
n = int(input())
a = input().split()
k = int(input())
z = n - a.count('a')
zzz = f(n) / (f(n - k) * f(k))
if z >= k:
	ans = zzz - f(z) / (f(z - k) * f(k))
	print(ans / zzz)
else:
	print(1.0)


import itertools
n = int(input())
c = 0
x = input().split(' ')
k = int(input())
m = []
m.extend(itertools.combinations(x, k))
z = 0
c = 0
for i in range(0, len(m)):
	if 'a' in m[i]:
		c += 1
	z += 1
p = c / z
print(p)


import operator
import itertools

def read_f(f):
	return f(input())

def read_f_words(f):
	return map(f, input().split())
n = read_f(int)
a = read_f_words(str)
k = read_f(int)
ways = list(itertools.combinations(a, k))
c = len(ways)
witha = len(list(filter(lambda x: x, map(lambda x: 'a' in x, ways))))
print(witha * 1.0 / c)


from itertools import combinations
i = input()
s = input().split(' ')
i = int(input())
comb = combinations(s, i)
t2 = len(list(comb))
comb = combinations(s, i)
temp = sum(['a' in z for z in comb])
print(temp / t2)


N = int(input())
S = input().split()
K = int(input())
from itertools import combinations
comb = combinations(S, K)
comb = list(comb)
ctr = 0
for c in comb:
	if 'a' in c:
		ctr += 1
print(ctr / len(comb))


import itertools
length = input()
ey = input().split(' ')
select_size = int(input())
a_in = 0
total = 0
for combo in itertools.combinations(ey, select_size):
	if 'a' in combo:
		a_in += 1
	total += 1
print(a_in / total)


from itertools import combinations
n = int(input())
word = list(input().split())
size = int(input())
total = 0
num = 0
L = combinations(range(0, n), size)
for l in L:
	total += 1
	for i in range(size):
		if word[l[i]] == 'a':
			num += 1
			break
print(float(num) / total)


from math import factorial
n = int(input())
data = input().split()
k = int(input())
m = n - data.count('a')
if k == 0 or m == 0:
	print(1)
elif m < k:
	print(1)
else:
	total = factorial(n) / (factorial(k) * factorial(n - k))
	other = factorial(m) / (factorial(k) * factorial(m - k))
	print((total - other) / total)


import itertools
N = int(input())
lis = list(input().split())
a = list(itertools.combinations(lis, int(input())))
count = 0
for i in a:
	if 'a' in i:
		count += 1
print(format(count / len(a), '.12g'))


from itertools import combinations
input()
getElements = ''.join(input().split())
getMaxIndex = int(input())
inputSet = set('a')
count = 0
getCombinationList = list(combinations(getElements, getMaxIndex))
for i in getCombinationList:
	if len(list(inputSet - set(i))) == 0:
		count += 1
print(round(count / len(getCombinationList), 3))


from itertools import combinations
N = int(input())
s = input().split()
K = int(input())
c = 0
c0 = 0
for i in combinations(s, K):
	c0 = c0 + 1
	if 'a' in i:
		c = c + 1
print(c / c0)


from itertools import combinations

def main():
	n = int(input())
	a = input().split()
	k = int(input())
	b = list(combinations(a, k))
	cnt = 0
	for i in b:
		if 'a' in i:
			cnt += 1
	print(cnt / len(b))
main()


N = int(input())
D = input().split()
K = int(input())
from itertools import combinations
contain = 0
total = 0
for c in combinations(D, K):
	if 'a' in c:
		contain += 1
	total += 1
print(contain / total)


f = [1]
for i in range(1, 10 + 1):
	f.append(i * f[-1])
n = int(input().strip())
inp = input().strip().split()
k = int(input().strip())
a = 0
na = 0
for i in inp:
	if i == 'a':
		a += 1
	else:
		na += 1
if k > na:
	print(1)
else:
	print(1 - f[na] * f[na + a - k] / (f[na + a] * f[na - k]))


import itertools
n = int(input())
st = input().split(' ')
k = int(input())
l = list(itertools.combinations(st, k))
print(len(list(filter(lambda x: 'a' in x, l))) / len(l))


import itertools
n = int(input())
a = [i for i in input().split()]
k = int(input())
(n, d) = (0, 0)
for x in itertools.combinations(a, k):
	if x.count('a') > 0:
		n += 1
	d += 1
print(n / d)


import sys
stdin = sys.stdin
n = int(stdin.readline())
a = stdin.readline().split()
k = int(stdin.readline())
u = 20
c = [[0] * u for _ in range(u)]
for i in range(u):
	c[i][0] = 1
	for j in range(1, i + 1):
		c[i][j] = c[i - 1][j] + c[i - 1][j - 1]
na = a.count('a')
print('{0:.3f}'.format(1 - c[n - na][k] / c[n][k]))


import string
symbols = string.ascii_lowercase
from itertools import combinations

def __starting_point():
	n = int(input().strip())
	arr = list(map(str, input().strip().split(' ')))
	times = int(input().strip())
	cmbts = list(combinations(sorted(arr), times))
	print('{:.4f}'.format(len(list([a for a in cmbts if a[0] == 'a'])) / len(cmbts)))
__starting_point()


import math
input()
letters = input().split(' ')
if len(letters) == 1:
	print(1.0 if letters[0] == 'a' else 0.0)
else:
	k = int(input())
	las = 0
	for l in letters:
		if l == 'a':
			las += 1
	if las == len(letters) or k > len(letters) - las:
		print(1.0)
	else:

		def bc(n, m):
			return math.factorial(m) // math.factorial(n) // math.factorial(m - n)
		print(1 - bc(k, len(letters) - las) / bc(k, len(letters)))


N = int(input())
letters = [c for c in input().split()]
a = letters.count('a')
K = int(input())
if N - a < K:
	print(1.0)
else:
	from math import factorial as f
	total = f(N) / f(N - K) * f(K)
	nota = f(N - a) / f(N - a - K) * f(K)
	print((total - nota) / total)


import itertools
n = int(input())
a = [x for x in input().split()]
k = int(input())
b = [x for x in itertools.combinations(a, k)]
total = len(b)
c = 0
ans = 0
for i in b:
	if 'a' in i:
		c += 1
ans = c / total
print(ans)


from itertools import combinations
n = int(input())
s = input().split()
k = int(input())
assert n == len(s)
total = valid = 0
for t in combinations(s, k):
	valid += 'a' in t
	total += 1
print('{:.3f}'.format(valid / total))


import functools

def factorial(n):
	if n == 0:
		return 1
	return functools.reduce(lambda a, b: a * b, range(1, n + 1))

def nchoosek(n, k):
	if k > n:
		return 0
	return factorial(n) / (factorial(k) * factorial(n - k))
n = int(input())
letters = input().split(' ')
k = int(input())
cntA = sum(map(lambda x: 1 if x == 'a' else 0, letters))
nSets = nchoosek(n, k)
nSetsWithoutA = nchoosek(n - cntA, k)
ans = (nSets - nSetsWithoutA) / nSets
print(ans)


def nCr(n, r):
	total = 1
	for i in range(n - r + 1, n + 1):
		total *= float(i)
	for i in range(2, r + 1):
		total /= float(i)
	return total
n = int(input())
s = list(input().split())
n2 = n - s.count('a')
r = int(input())
total = nCr(n, r)
notA = nCr(n2, r)
out = float(total - notA) / total
print(out)


from itertools import combinations
list_len = int(input())
data = input().strip().split()
k = int(input())
a_indexes = [ind + 1 for (ind, val) in enumerate(data) if val == 'a']
outcomes = list(combinations(data, k))
m = len(list(filter(lambda item: 'a' in item, outcomes)))
n = len(outcomes)
print(m / n)


N = int(input())
s = input().split()
k = int(input())
val = 1.0
a = s.count('a')
for x in range(k):
	val *= (N - a - x) / (N - x)
print('{0:.3f}'.format(1 - val))


from itertools import combinations
n = int(input())
s = input().split(' ')
k = int(input())
k_indices = 0
total = 0
for j in combinations(s, k):
	for i in list(j):
		if i in ['a']:
			k_indices += 1
			break
	total += 1
print(k_indices / total)


import itertools
n = int(input())
arr = list(map(str, input().split()))
k = int(input())
st = ''
for i in arr:
	st += i
com = [list(itertools.combinations(st, x)) for x in range(1, len(st) + 1)]
scom = [''.join(e) for e in sum(com, [])]
cnt = 0
acnt = 0
for i in scom:
	if len(i) == k:
		cnt += 1
		if 'a' in i:
			acnt += 1
x = acnt / cnt
g = float('{0:.4f}'.format(x))
print(g)


from itertools import combinations
N = int(input())
tempList = list(range(1, N + 1))
Chars = list(input().split())
num = int(input())
comb = list(combinations(tempList, num))
indexOfa = set()
for i in range(N):
	if Chars[i] == 'a':
		indexOfa.add(i + 1)
occur = 0
for elem in comb:
	if not indexOfa.isdisjoint(elem):
		occur = occur + 1
prob = occur / len(comb)
print('{}'.format(prob))


from itertools import combinations
l = int(input())
stl = list(input().split())
c = int(input())
stri = ''
for i in stl:
	stri = stri + i
combs = list(combinations(stri, c))
mainctr = 0
for i in combs:
	ctr = 0
	for j in i:
		if j == 'a':
			ctr = 1
			break
	if ctr == 0:
		mainctr = mainctr + 1
print(1 - mainctr / len(combs))


from itertools import *
N = int(input())
line = input()
letters = line.split()
K = int(input())
total = 0
wanted = 0
letters.sort()
for x in combinations(letters, K):
	total += 1
	if x[0] == 'a':
		wanted += 1
print(wanted / total)


import sys
from math import factorial

def C(n, k):
	return factorial(n) / (factorial(k) * factorial(n - k))

def ans(n, k, x):
	if n - x - k >= 0:
		return 1 - C(n - x, k) / C(n, k)
	else:
		return 1
rl = lambda : sys.stdin.readline()
n = int(rl())
s = rl().split()
x = s.count('a')
k = int(rl())
print('{:.4f}'.format(ans(n, k, x)))


from itertools import combinations
input()
S = input().split()
X = int(input())
c = 0
L = list(combinations(S, X))
for i in L:
	if 'a' in i:
		c += 1
print(c / len(L))


def cum_prod(a, b):
	res = b
	for i in range(a, b):
		res *= i
	return res
N = int(input())
M = sum((c == 'a' for c in input().split()))
K = int(input())
print(1 - cum_prod(N - K - M + 1, N - K) / cum_prod(N - M + 1, N)) if M != 0 else print(0.0)