#include <bits/stdc++.h>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int v[15]= {0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712};
int a1[15]= {0,1};
int a4[15]= {0,2,4,1,3};
int a5[15]= {0,1,3,5,2,4};
int a6[15]= {0,2,4,6,1,3,5};
int a7[15]= {0,1,3,5,7,2,4,6};
int a8[15]= {0,1,5,8,6,3,7,2,4};
int a9[15]= {0,1,3,6,8,2,4,9,7,5};
int a10[15]= {0,1,3,6,8,10,5,9,2,4,7};
int a11[15]= {0,1,3,5,7,9,11,2,4,6,8,10};
int a12[15]= {0,1,3,5,8,10,12,6,11,2,7,9,4};
int a13[15]= {0,1,3,5,2,9,12,10,13,4,6,8,11,7};

int main()
{
    int n,i;
    f>>n;
    if(n==1)
        g<<1;
    else if(n==2||n==3)
        g<<0;
    else if(n==4)
        for(i=1; i<=n; i++)
            g<<a4[i]<<" ";
    else if(n==5)
        for(i=1; i<=n; i++)
            g<<a5[i]<<" ";
    else if(n==6)
        for(i=1; i<=n; i++)
            g<<a6[i]<<" ";
    else if(n==7)
        for(i=1; i<=n; i++)
            g<<a7[i]<<" ";
    else if(n==8)
        for(i=1; i<=n; i++)
            g<<a8[i]<<" ";
    else if(n==9)
        for(i=1; i<=n; i++)
            g<<a9[i]<<" ";
    else if(n==10)
        for(i=1; i<=n; i++)
            g<<a10[i]<<" ";
    else if(n==11)
        for(i=1; i<=n; i++)
            g<<a11[i]<<" ";
    else if(n==12)
        for(i=1; i<=n; i++)
            g<<a12[i]<<" ";
    else if(n==13)
        for(i=1; i<=n; i++)
            g<<a13[i]<<" ";
    g<<'\n'<<v[n];
    return 0;
}