#include <fstream>
using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
 
int n;
int sol[15];
int col[15];
int dp[30];
int ds[30];
int nrVar=0;
 
void afisare()
{
    for(int i=1;i<=n;i++)
        cout<<sol[i]<<" ";
    cout<<endl;
}
 
bool verifica(int pas,int i)
{
    if(col[i] || dp[n-i+pas] || ds[i+pas-1])
        return false;
 
    return true;
}
 
void backtr(int pas)
{
    for(int i=1;i<=n;i++)
    {
        if(verifica(pas,i))
        {
            sol[pas]=i;
 
            col[i]=1;
            dp[n-i+pas]=1;
            ds[i+pas-1]=1;
 
            if(nrVar==0 && pas==n)
                afisare();
 
            if(pas==n)
                 nrVar++;
            else
                backtr(pas+1);
 
            col[i]=0;
            dp[n-i+pas]=0;
            ds[i+pas-1]=0;
 
        }
    }
}
 
int main()
{
    cin>>n;
 
    for(int i=1;i<30;i++)
    {
        dp[i]=0;
        ds[i]=0;
        if(i<15)
            col[i]=0;
    }
 
    backtr(1);
 
    cout<<nrVar;
 
    return 0;
}