#include <bits/stdc++.h>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, st[15], fr[15], nr;

int Ver(int top)
{
    for(int i = 1; i < top; i++)
        if(top - i == st[top] - st[i] || top + st[top] == i + st[i]) return 0;
    return 1;
}

void Back(int top)
{
    int i;
    for(i = 1; i <= n; i++)
    {
        if(fr[i] == 0)
        {
            fr[i] = 1;
            st[top] = i;
            if(Ver(top))
            {
                if(top == n)
                {
                    if(nr == 0)
                        for(int j = 1; j <= n; j++)
                            fout << st[j] << " ";
                    nr++;
                }
                else Back(top + 1);
            }
            fr[i] = 0;
        }
    }
}

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