#include <bits/stdc++.h>

using namespace std;
int n, ok, sol[30], d1[30], d2[30], col[30], nr;
void back(int k)
{
    int i;
    if(k == n + 1)
    {
        nr++;
        if(!ok)
        {   for(i = 1; i <= n; i++)
                printf("%d ", sol[i]);
            ok = 1;
        }
        return;
    }
    for(i = 1; i <= n; i++)
        if(!col[i] && !d1[n - k + i] && !d2[k + i - 1])
        {
            d1[n - k + i] = 1;
            d2[k + i - 1] = 1;
            col[i] = 1;
            sol[k] = i;
            back(k + 1);
            d1[n - k + i] = 0;
            d2[k + i - 1] = 0;
            col[i] = 0;
        }
}
int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &n);
    back(1);
    printf("\n%d", nr);
    return 0;
}