1324.
座位安排
时间限制 1000 ms
内存限制 128 MB
考场里的座位恰好有$n$行$m$列,并且恰好有 $n\times m$位考生在这个考场里面考试。也就是说,所有的座位上都有考生。
hzy根据学校记载,有$k$位考生可能作弊,因此hzy不能让他们之中的任何两个人做在相邻的座位上!所谓相邻的座位,即在同一行相邻列或者在同一列的相邻行的座位。hzy准备这样安排座位,首先随机选择一种方案,如果这种方案是合法的,就用这种方案,否则重新选择。你的任务是计算,他得到一个合法方案时,需要的期望选择次数。
输入数据
输出数据
如果不存在合法的方案,则输出Impossible!,否则输出一个分数$p/q$,表示期望选择次数(即平均次数),这里$p$和$q$应该是互质的。
样例输入
复制
input1
1 4 3
input2
2 3 2 \n
· · \n
\n
· · \n
样例输出
复制
input1
Impossible!
input2
15/8 \n
\n
\n
\n
样例说明
$1≤n≤80,1≤m≤80,1≤n*m≤80$
$0≤k≤20$,并且$k≤n*m$