# CFR 285 D. Permutation Sum ( Meet in the Middle, Search )

Problem - D - Codeforces

The single line contains integer n (1 ≤ n ≤ 16).
TL: 1500 ms
ML: 256 MB

```#include <bits/stdc++.h>
using namespace std;

const int MOD = ( int ) 1e9 + 7;

int N;
int mp[ 1 << 15 ];
int dp[ 6500 ][ 6500 ];

void pre_dfs( int x, int s, int t ){
if( x == N / 2 ){
++dp[ mp[ s ] ][ mp[ t ] ];
return;
}
for( int y = 0; y < N; ++y ){
if( s >> y & 1 ) continue;
if( t >> ( x + y ) % N & 1 ) continue;
pre_dfs( x + 1, s | 1 << y, t | 1 << ( x + y ) % N );
}
}

void dfs( int x, int s, int t, int &ans ){
if( x == N ){
( ans += dp[ mp[ ( 1 << N ) - 1 ^ s ] ][ mp[ ( 1 << N ) - 1 ^ t ] ] ) %= MOD;
return;
}
for( int y = 0; y < N; ++y ){
if( s >> y & 1 ) continue;
if( t >> ( x + y ) % N & 1 ) continue;
dfs( x + 1, s | 1 << y, t | 1 << ( x + y ) % N, ans );
}
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
if( ~N & 1 ){
cout << 0 << endl;
exit( 0 );
}
for( int s = 0; s < 1 << N; ++s ){
if( __builtin_popcount( s ) != N / 2 ) continue;
static int cnt = 0;
mp[ s ] = cnt++;
}
int ans = 0;
pre_dfs( 0, 0, 0 );
dfs( N / 2, 0, 0, ans );
for( int i = 1; i <= N; ++i ){
ans = 1LL * ans * i % MOD;
}
cout << ans << endl;
return 0;
}
```