方格染色

【题目描述】

游戏在一个由$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$。