[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

#include <cstdio>
 
int n, line, res;
 
//ld is \, rd is /
void solve(int level, int horizon, int ld, int rd){
    if(level == n) res++;
    else {
        int ok = (~(horizon | ld | rd)) & line, i;
        while(ok){
            i = ok & -ok;
 
            solve(level+1, horizon | i, (ld | i)>>1, (rd | i)<<1);
 
            ok ^= i;
        }
    }
}
 
int main(){
    scanf("%d", &n);
 
    line = (1<<n)-1;
 
    solve(0, 0, 0, 0);
    printf("%d\n", res);
 
    return 0;
}