일단 답이 되려면 p는 항상 이런 꼴을 가져야 함


x -> x

x -> y -> x

x -> y -> x+1 -> y+1 -> x, 혹은 이것의 방향을 뒤집은것



그래서 일단 (x,x+1)처럼 연속된 2개를 일단 많이 만들거임. i개를 만들었다고 해보자


그러면 i개를 2개씩 이어서 (x,x+1,y,y+1)을 묶어놓으면, 여기서 x->y->x+1->y+1->x를 만들 수 있음

그래서 2개씩 잇는 방법이 fact[i] / (2^(i/2)*fact[i/2]), 그런데 여기서 (x,x+1,y,y+1)을 골랐을때 여기서 나올 수 있는 사이클이 일단 2개씩 생기고, (x,x+1,y,y+1)쌍은 총 i/2개 있으니 여기서 경우의수가 2^(i/2)가 곱해짐


이제 남은 1개씩을 적당히 연속된 2개묶음들 사이에 넣을건데, 빈칸은 i+1개고 넣어야 하는 수는 N-2i개니까 1을 잘 넣는 경우의 수가 총 N-2iCN-i개가 됨

이제 넣은 1개묶음을 또 2개씩 묶어서, x->y->x를 만들거임. 이거는 미리 DP로 계산하는데

대충 1개 묶음의 개수가 k개라고 하면, 얘를 2개씩 적당히 묶어서 x->x 혹은 x->y->x들로 만드는 경우의 수를 count[k]라고 할때,

count[0] = count[1] = 1, count[k] = count[k-1] + (k-1) * count[k-2]가 됨.


이제 모든 i에 대해서 이제 경우의 수를 다 합하면 됨.


2*i가 N이하가 되는 모든 0이상의 i에 대해서, fact[i] / (2^(i/2)*fact[i/2]) * 2^(i/2) * (N-2i)C(N-i) * count[N-2*i] 를 전부 더하면 됨

이건 그냥 O(N)임 혹은 O(N log(MOD))


그런데 이걸 시발 못품 1시간 내내 (x,x+1,y,y+1)을 묶는 방법이 fact[i] / (2^(i/2)*fact[i/2])가 아니고 fact[i] / (2^(i/2))라고 생각해서 하 자살마렵다