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つしかない。何もしない（$\sigma$は恒等置換)、または学生の順序を逆にするものである。

$n=6$の場合、ベッドペア$(1, 2)(3, 4)(5, 6)$とデスクペア$(3, 6)(4, 5)$には、条件を満たす8つの順列がある。1つの例は、写像$(1, 2, 3, 4, 5, 6)\mapsto(1, 2, 5, 6, 3, 4)$である。

$n=36$の場合、次のベッドペアがあり、 $(2,13)(4,30)(5,27)(6,16)(10,18)(12,35)(14,19)(15,20)(17,26)(21,32)(22,33)(24,34)(25,28)$またデスクペアは次とすると、 $(1,35)(2,22)(3,36)(4,28)(5,25)(7,18)(9,23)(13,19)(14,33)(15,34)(20,24)(26,29)(27,30)$ $36!$の可能な順列（恒等順列を含む）のうち、663552個が学生によって規定された条件を満たす。

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

1,3
2,4

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