座位安排

座位安排

测试数据来自 system/1286

背景

快要期中考试了!老师需要hzy帮他排考试的座位。。。

描述

考场里的座位恰好有n行m列,并且恰好有n*m位考生在这个考场里面考试,也就是说,所有的座位上都有考生。hzy根据学校记载,有k位考生可能作弊,因此hzy不能让他们之中的任何两个人做在相邻的座位上!所谓相邻的座位,即在同一行相邻列或者在同一列的相邻行的座位。hzy准备这样安排座位,首先随机选择一种方案,如果这种方案是合法的,就用这种方案,否则重新选择。你的任务是计算,他得到一个合法方案时,需要的期望选择次数。

格式

输入格式

输入文件为一行,仅包含三个整数n,m和k。

输出格式

如果不存在合法的方案,则输出文件seating.out中应该包含Impossible!,否则输出一个分数p/q,表示期望选择次数(即平均次数),这里p和q应该是互质的。

样例1

样例输入1

1 4 3

样例输出1

Impossible!

样例2

样例输入2

2 3 2

样例输出2

15/8

提示

1≤n≤80,1≤m≤80,1≤n*m≤80
0≤k≤20,并且k≤n*m

信息

ID
1406
难度
(无)
分类
动态规划 | 状态压缩DP数论 | 欧几里得算法 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者