#include <fstream>

using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int n, cnt, x[20];
bool  gasit = 0;
void afis()
{
    if(!gasit)
    {
        for(int i=1; i<=n; i++)
        cout << x[i] << " ";
        cout << '\n';
    }

    cnt++;

}
bool valid(int k)
{
    for(int i=1; i<k; i++)
        if(x[k] == x[i])
            return 0;
        for(int i=1; i<k; i++)
    if(k - i == abs(x[k] - x[i]))
        return 0;
    return 1;
}
void bkt(int k)
{
    for(int i=1; i<=n; i++)
    {
        x[k] = i;
        if(valid(k))
            if(k == n)
            {
                afis();
                gasit = 1;
            }

            else
                bkt(k+1);
    }
}
int main()
{
    cin >> n;
    bkt(1);
    cout << cnt;
    return 0;
}