← Problem 672

Beds and Desks

Problem 674 →

Beds and Desks

Problem 673

At Euler University, each of the students (numbered from 1 to ) occupies a bed in the dormitory and uses a desk in the classroom.
Some of the beds are in private rooms which a student occupies alone, while the others are in double rooms occupied by two students as roommates. Similarly, each desk is either a single desk for the sole use of one student, or a twin desk at which two students sit together as desk partners.
We represent the bed and desk sharing arrangements each by a list of pairs of student numbers. For example, with , if represents the bed pairing and the desk pairing, then students 2 and 3 are roommates while 1 and 4 have single rooms, and students 1 and 3 are desk partners, as are students 2 and 4.
The new chancellor of the university decides to change the organisation of beds and desks: he will choose a permutation of the numbers and each student will be given both the bed and the desk formerly occupied by student number .
The students agree to this change, under the conditions that:
  • Any two students currently sharing a room will still be roommates.
  • Any two students currently sharing a desk will still be desk partners.
    • In the example above, there are only two ways to satisfy these conditions: either take no action ( is the identity permutation), or reverse the order of the students.
    With , for the bed pairing and the desk pairing , there are 8 permutations which satisfy the conditions. One example is the mapping .
    With , if we have bed pairing:

    and desk pairing

    then among the     possible permutations (including the identity permutation), 663552 of them satisfy the conditions stipulated by the students.
    The downloadable text files beds.txt and desks.txt contain pairings for . Each pairing is written on its own line, with the student numbers of the two roommates (or desk partners) separated with a comma. For example, the desk pairing in the example above would be represented in this file format as:
    1,32,4
    With these pairings, find the number of permutations that satisfy the students' conditions. Give your answer modulo .