#arc076a. [arc076_a]Reconciled?
[arc076_a]Reconciled?
問題文
すぬけ君は、犬を 匹と猿を 匹飼っています。すぬけ君は、この 匹を一列に並べようと思っています。
文字通り犬猿の仲の犬たちと猿たちを仲直りさせたいすぬけ君は、犬同士、または猿同士が隣り合うところができないように並べようと思っています。
このような並べ方は何通りあるでしょうか。犬と猿は 以上の数を理解できないので、並べ方の個数を で割ったあまりを求めてください。 ただし、犬同士、また猿同士は互いに区別します。また、左右が反転しただけの列も異なる列とみなします。
制約
入力
入力は以下の形式で標準入力から与えられる。
出力
並べ方の個数を で割ったあまりを出力せよ。
入力例 1
2 2
出力例 1
8
犬をそれぞれ A
,B
とし、猿をそれぞれ C
,D
とすると、ACBD
,ADBC
,BCAD
,BDAC
,CADB
,CBDA
,DACB
,DBCA
の 通りの並べ方があります。
入力例 2
3 2
出力例 2
12
入力例 3
1 8
出力例 3
0
入力例 4
100000 100000
出力例 4
530123477