#include <bits/stdc++.h>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int st[20],n,f[20],sol;

void afisare(int vf)
{
    int i;
    for(i=1;i<=vf;i++)
        fout<<st[i]<<" ";
    fout<<"\n";
}

void back(int vf)
{
    int i;

    for(i=1;i<=n;i++)
        if(f[i]==0 and i!=st[vf-1]+1 and i!=st[vf-1]-1)
    {
        f[i]++;
        st[vf]=i;
        if(vf==n and sol==0)afisare(vf),sol++;
        else if(vf==n)sol++;
        else back(vf+1);
        f[i]--;

    }
}
int main()
{
    fin>>n;
    back(1);
    fout<<sol<<"\n";
    return 0;
}