#include<cstdio>
    using namespace std;
    #define MAX 15
    int N , k , st[MAX] ,sol;
    bool l[MAX] , d1[2*MAX] , d2[2*MAX],sw;

    void back(int k);
    void write();

    int main()
    {
        freopen("damesah.in" , "r" , stdin );
        freopen("damesah.out" , "w" , stdout );
        scanf("%d" , &N );
        back(1);
        printf("\n%d" , sol);
        return 0;
    }

    void back(int k)
    {
        for(int i = 1 ; i <= N ; ++i )
        {
            if(l[i] || d1[k-i+N] || d2[k+i])
                continue;
            d1[k-i+N] = d2[k+i] = l[i] = 1;
            st[k] = i;
            if(k == N)
            {
                if(!sw)
                    write(),sw = 1;
                sol++;
            }
            else
                back(k+1);
            d1[k-i+N] = d2[k+i] = l[i] = 0;
        }
    }

    void write()
    {
        for(int i = 1 ; i <= N ; ++i )
            printf("%d " , st[i] );
    }