673 : ベッドと机

オイラー大学では、1から $n$ までの番号が付けられた $n$ 人の学生が、それぞれ寮のベッドと教室の机を割り当てられる。

ベッドには、学生が1人で占有する個室にあるものと、2人の学生がルームメイトとして入っている二人部屋にあるものとがある。同様に、各々の机は、1人の学生のみが使用するシングルデスクか、2人の学生がデスクパートナーとして一緒に座るツインデスクのいずれかである。

ベッドとデスクの共有の取り決めは、それぞれ学生番号のペアのリストで表される。たとえば、$n=4$で、$(2,3)$がベッドのペアを表し、$(1,3)(2,4)$がデスクのペアを表す場合、学生2と3はルームメイトであり、1と4は個室を持ち、学生1と3はデスクパートナーであり、学生2と4も同様である。

大学の新しい学長は、ベッドと机の構成を変更することを決定した。すなわち、数$1, 2, \dots, n$の順列$\sigma$が選択され、各学生$k$には、以前は学生番号$\sigma(k)$が使っていたベッドと机の両方が与えられる。

学生は、次の条件の下で、この変更に同意する。

1. 現在部屋を共有している2人の学生は、引き続きルームメイトになる。

2. 現在デスクを共有している2人の学生は、引き続きデスクパートナーになる。

上記の例では、これらの条件を満たす方法は2つしかない。何もしない（は恒等置換)、または学生の順序を逆にするものである。

の場合、ベッドペアとデスクペアには、条件を満たす8つの順列がある。1つの例は、写像である。

の場合、次のベッドペアがあり、 またデスクペアは次とすると、 の可能な順列（恒等順列を含む）のうち、663552個が学生によって規定された条件を満たす。

ダウンロード可能なテキストファイルおよび に のペアが入っている。各ペアは、2人のルームメイト（またはデスクパートナー）の学生番号をカンマで区切って、一行に記述される。たとえば、前述のの例のデスクペアはをこのファイル形式で表すと次のようになる：

これらの組み合わせで、受講者の条件を満たす順列の個数を見つけよ。を法として答えよ。