CF1275D.Storage2

Для надежного, но компактного хранения картинок во ВКонтакте используются избыточные коды. Все картинки разбиваются на группы по 15, и для каждой группы картинок вычисляются 13 избыточных кодов. Избыточные коды необходимы, чтобы суметь восстановить некоторые картинки, если они будут утеряны вследствие поломки жесткого диска.

Перед вычислением избыточных кодов 15 картинок из одной группы записываются в матрицу из 3 строк и 5 столбцов. Далее к получившейся матрице справа добавляются два столбца с 6 избыточными кодами (каждая пара кодов вычисляется на основе картинок в той же строке), а затем снизу добавляется еще одна строка из 7 избыточных кодов (каждый из них считается на основе картинок или избыточных кодов в том же столбце).

Будем называть картинки и избыточные коды блоками. Таким образом, из 15 картинок мы получили 28 блоков, расставленных в виде матрицы 4 на 7. В данной задаче вам не будут даны формулы вычисления избыточных кодов, но даны их свойства: а именно по 3 любым блокам из одного столбца можно однозначно восстановить утерянный четвертый блок в том же столбце, а также по 5 любым блокам из одной строки можно однозначно восстановить оставшиеся два из той же строки, если они были утеряны. Естественно, операцию восстановления можно применять несколько раз к разным строкам и столбцам в любом порядке, а также в следующих операциях использовать блоки, восстановленные ранее.

Пусть у вас есть 28 блоков (15 картинок и 13 избыточных кодов), и вы потеряли случайные $k$ из них (равновероятно среди всех вариантов). Ваша задача посчитать вероятность, что хотя бы одну из 15 картинок будет невозможно восстановить, а также матожидание количества потерянных картинок.

为在 VKontakte 中实现可靠且紧凑的图片存储，采用了冗余编码技术。所有图片被分为每组 15 张，对每组图片计算出 13 个冗余码。这些冗余码的作用是在硬盘损坏导致部分图片丢失时，能够恢复其中一些图片。

在计算冗余码之前，将同一组中的 15 张图片排布成一个 $3$ 行 $5$ 列的矩阵。随后，在该矩阵右侧添加两列共 $6$ 个冗余码（每对冗余码基于同一行中的图片计算得出）；再在矩阵下方添加一行共 $7$ 个冗余码（每个冗余码基于同一列中的图片或已有的冗余码计算得出）。

我们将图片和冗余码统称为“数据块”。由此，从最初的 15 张图片出发，我们最终得到 $28$ 个数据块，并排布成一个 $4 \times 7$ 的矩阵。本题中不提供冗余码的具体计算公式，但给出其关键性质：

• 在任意一列中，只要存在其中任意 $3$ 个数据块，即可唯一地恢复该列中缺失的第 $4$ 个数据块；
• 在任意一行中，只要存在其中任意 $5$ 个数据块，即可唯一地恢复该行中缺失的其余 $2$ 个数据块。

显然，恢复操作可对不同行与列多次执行，且顺序任意；后续操作中亦可使用此前已恢复出的数据块。

现设你拥有全部 $28$ 个数据块（含 $15$ 张原始图片与 $13$ 个冗余码），并随机丢失其中 $k$ 个（所有 $\binom{28}{k}$ 种丢失方式等概率）。你的任务是：

1. 计算至少有一张原始图片无法被恢复的概率；
2. 计算丢失的原始图片数量的数学期望值。

В единственной строке входных данных записано целое число $k$ ($0 \le k \le 28$) — количество потерянных блоков.

输入数据的唯一一行中包含一个整数 $k$（$0 \le k \le 28$），表示丢失的方块数量。

Выведите два числа — вероятность, что хотя бы одну картинку невозможно восстановить из оставшихся блоков, и матожидание количества картинок, которые невозможно восстановить из оставшихся блоков.

Ответы будут считаться корректными, если их абсолютная или относительная погрешность не превосходит $10^{-9}$.

输出两个数：至少有一张图片无法从剩余的数据块中恢复的概率，以及无法从剩余的数据块中恢复的图片数量的数学期望。

若答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

В первом примере утеряны все 28 блоков, очевидно, с 100% вероятностью потеряны все 15 картинок.

Во втором примере только в 210 случаев из 376740 будет невозможно восстановить хотя бы одну картинку, поэтому вероятность $210/376740$. В зависимости от расположения утерянных блоков будет невозможно восстановить от 1 до 6 картинок, матожидание равно $15/8372$.

Приведены два возможных способа потерять 6 блоков.

На первом случае утеряны 3 картинки и 3 избыточных кода (отмечены крестиками). Вначале мы можем восстановить один утерянный блок в первой строке (используя 5 других из этой же строки) и восстановить два утерянных блока в четвертой строке (используя 5 других из той же строки). Затем мы можем восстановить три оставшихся блока (используя 3 других блока из соответствующих столбцов). Заметим, что при восстановлении по столбцу мы использовали в том числе и восстановленные на первом шаге блоки. Таким образом, нам удалось восстановить все блоки и не было потеряно ни одной картинки.

На втором случае утеряны 4 картинки и 2 избыточных кода. Во второй и третьей строках по три утерянных блока, а значит мы не можем однозначно восстановить ни один из блоков в них. Аналогично, в третьем, пятом и седьмом столбцах по два утерянных блока, а значит мы не можем однозначно восстановить ни один из блоков в них. В остальных строках и столбцах все блоки остались целыми, восстанавливать нечего. Таким образом, нам не удастся восстановить ни один из шести утерянных блоков, но только из четыре из них были картинками.

在第一个例子中，全部28个数据块均丢失，显然所有15张图片都以100%的概率丢失。

在第二个例子中，仅在376740种情况中的210种情况下，至少有一张图片无法恢复，因此概率为 $210/376740$。根据丢失数据块的位置不同，无法恢复的图片数量为1至6张不等，期望值为 $15/8372$。

给出了两种可能的丢失6个数据块的情形。

第一种情形中，丢失了3张图片和3个冗余校验块（用“×”标记）。首先，我们可利用该行其余5个未丢失的数据块恢复第一行中一个丢失的数据块，并利用该行其余5个未丢失的数据块恢复第四行中两个丢失的数据块；随后，再利用各对应列中其余3个未丢失的数据块恢复剩余的3个丢失数据块。注意：在按列恢复时，我们所使用的数据块中也包括了第一步中已恢复出的数据块。因此，所有数据块均被成功恢复，没有任何一张图片丢失。

第二种情形中，丢失了4张图片和2个冗余校验块。第二行与第三行各有3个丢失的数据块，因此这两行中任一丢失的数据块均无法唯一确定并恢复；同理，第三列、第五列与第七列也各有2个丢失的数据块，因此这些列中任一丢失的数据块亦无法唯一确定并恢复。其余各行与各列中的所有数据块均完好无损，无需恢复。因此，6个丢失的数据块均无法恢复，但其中仅有4个是图片数据块。