题目描述

游戏在一个由$n×n$个方格组成的正方形棋盘上进行，首先在每个方格上均匀随机地填入$1$到$m$之间的正整数（每个方格填的数均不同），然后小可可均匀随机地选出$k$个$1$到$m$的数字（可能选的数不在棋盘上），把它们出现在棋盘上的方格涂黑，设有$r$行被整行涂黑，有$c$列被整列涂黑，小可可便可以得到$2^{r+c}$分。 现在小可可想知道他的期望得分是多少。

输入

第一行包含三个正整数$n,m,k$。

输出

一行包含一个实数，表示期望得分，如果答案$>10^{99}$，就输出$10^{99}$，输出被认为正确当且仅当你的输出与标准输出的相对误差不超过$10^{-6}$。

输入样例

1 2 1

输出样例

2.5

提示

【样例解释】 在$1×1$的方格中填入$1$，选$1$或$2$，得分分别为$2^2=4$和$2^0=1$；在$1×1$的方格中填入$2$，选$1$或$2$，得分分别为$2^0=1$和$2^2=4$，所以期望得分为$\frac{4+1+1+4}{4}=2.5$。 【数据规模】 对于30%的数据，$2≤n≤5，m≤10$。 对于60%的数据，$2≤n≤10，m≤200$。 对于100%的数据，$2≤n≤300，n^2≤m≤100000， n≤k≤m$。

样例范围说明

提示中的完整范围从n=2开始，但公开样例n=1；本题也接受该已明确展示的n=1情况，公式与判题规则一致。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。