宾果游戏是在 5 × 5 方格上进行的,其中填充了 1 到 75 之间的不同数字。在本问题中,您将考虑在 n × n 网格上进行的通用版本,其中包含 1 到 m (m ≥ n2) 之间的不同数字。
玩家首先选择随机生成的宾果网格(在所有可用网格中统一生成)。然后将随机调用 1 到 m 之间的 k 个不同的数字(在所有可用的 k 个数字集合中统一调用)。对于出现在网格上的每个被叫号码,玩家标记该单元格。最后的分数是 2 的幂(完全标记的行数加上完全标记的列数)。
确定分数的期望值。预期分数可能会很大。如果预期分数大于 1099,则打印 1099(例如,不带引号的“1e99”)。
输入
输入将由三个整数 n、m、k 组成(1 ≤ n ≤ 300;n2 ≤ m ≤ 100000;n ≤ k ≤ m)。
输出
打印 1099 和预期分数中较小的一个。您的答案必须正确,绝对误差或相对误差在 10 - 9 之间。
示例
输入 #1
1 2 1
输出 #1
2.5
输入 #2
2 4 3
输出 #2
4
输入 #3
7 59164 40872
输出 #3
3.1415926538