Задача K. Bad game

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В ДВФУ при оценке выполнения студентами заданий используется система AWorks, которая снижает баллы за не вовремя сданное задание. Однажды преподаватель решил больше не мучить студентов и разработал игру, в которой нужно уничтожать монстров, давая им задания.

Всего в игре M монстров, им даётся N заданий. Каждый монстр характеризуется успешностью pi — это вероятность, с которой он сдаст задание вовремя. За вовремя сданное задание монстр получает 1 балл, за не вовремя сданное задание — 0.5 балла. Монстру необходимо заработать не менее A баллов.

Какое количество монстров заработает не менее A баллов и не будут уничтоженными? Найдите распределение вероятностей.

Монстры действуют независимо друг от друга, и сдача одного задания не зависит от сдачи другого задания.

Формат входного файла

Входной файл содержит целые числа N A M, за которыми следуют M вещественных чисел pi.

Формат выходного файла

Требуется вывести в выходной файл M + 1 пар чисел k ck, где k = 0, 1, ..., M, а ck — вероятность того, что ровно k монстров не будут уничтожены, с точностью до 5-ти знаков после запятой.

Ограничения

1 ≤ A ≤ N ≤ 10

1 ≤ M ≤ 10

0.01 ≤ pi ≤ 1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3 2
0.5 0.3
0 0.20366
1 0.55689
2 0.23946
2
3 1 1
0.1
0 0.00000
1 1.00000

0.117s 0.021s 13