#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, rez[15], col[15], dp[30], ds[30], ans;
void show()
{
        for(int i = 1; i <= n; i++) fout << rez[i] << " ";
        fout << "\n";
}
bool whoke(int poz,int i)
{
        return !col[i] && !dp[n - i + poz] && !ds[i + poz - 1];
}

void bak(int poz)
{
        for(int i = 1; i <= n; i++)
        {
                if(whoke(poz, i))
                {
                        rez[poz] = i, col[i] = 1, dp[n - i + poz] = 1, ds[i + poz - 1] = 1;
                        if(!ans && poz == n) show();
                        if(poz == n) ans++;
                        else bak(poz + 1);
                        col[i] = 0, dp[n - i + poz] = 0, ds[i + poz - 1] = 0;
                }
        }
}

int main()
{
    fin >> n;

    for(int i = 1; i < 30; i++)
    {
        dp[i] = 0, ds[i] = 0;
        if(i < 15) col[i] = 0;
    }
    bak(1);
    fout << ans;

    return 0;
}