#include <fstream>

using namespace std;

int sol[15];
int col[15];
int d1[35];
int d2[35];
int n,cate;

#define d2 (d2+13)

ifstream cin("damesah.in");
ofstream cout("damesah.out");

void backtr(int poz)
{
    if(poz==(n+1))
    {
        cate++;

        if(cate>1)
            return;

        cout<<sol[1];
        for(int i=2;i<=n;i++)
            cout<<' '<<sol[i];
        cout<<'\n';

        return;
    }

    for(int i=1;i<=n;i++)
    {
        if(!col[i] && !d1[poz+i-1] && !d2[poz-i])
        {
            sol[poz]=i;
            col[i]=1;
            d1[poz+i-1]=1;
            d2[poz-i]=1;

            backtr(poz+1);

            col[i]=0;
            d1[poz+i-1]=0;
            d2[poz-i]=0;
        }
    }
}

int main()
{
    cin>>n;

    backtr(1);
    cout<<cate<<'\n';

    cin.close();
    cout.close();
    return 0;
}