Right before the day of the final exam, a teacher is busy coming up with a seating assignment for the venue. The seats in the exam venue are arranged as m rows, each containing n seats, i.e., an m by n grid. The total number of students is exactly the same as the total number of seats, so all the seats will be occupied.
The teacher's task is complicated by the fact that there are k students who are suspected cheaters. In order to prevent cheating, the teacher will not allow any two suspected cheaters to sit in adjacent seats. Two seats are adjacent if and only if they are in adjacent columns of the same row, or adjacent rows of the same column.
The teacher's method for assigning the seats is simple. She finds a random seating assignment. Then, she checks if there are any suspected cheaters assigned to adjacent seats. If so, she repeats the process by finding another random assignment, and otherwise, she is done.
Your job is to determine the expected number of random seating assignments the teacher must generate before she finishes her task. Return this expected number as a String formatted "p/q" (quotes for clarity only), where p and q are relatively prime positive integers with no leading zeros. If there is no valid seating assignment, return "Impossible!" (quotes for clarity only).
|