Beat LR

正の整数 が与えられます。ここで、 は の倍数であることが保証されます。

の順列 であって、次の条件が満たされるものの個数を で割った余りを答えてください。

• を満たす全ての整数 について、 と のうち片方のみが満たされるものが存在しない。ただし、 、 とする。

• は整数
• は の倍数

N

答えを出力してください。

3

6

この場合、 ならば隣り合う要素は であるため条件を満たし、 ならば隣り合う要素に が含まれるため条件を満たします。よって、求めるべき答えは です。

12

47029248

この場合、条件は ならば 、 ならば となります。

9982443

198511167

で割った余りを答えることに注意してください。