#include <fstream>

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

    }

   return 1;

}
void bkt(int k)
{
    if(k <= n)
    {
        for(int i=1; i<=n; i++)
        {
            if(!viz[i])
            {
                bool ok= true;
                for(int j=1; j<k; j++)
                    if(k - j == abs(x[j] - i))
                        ok = false;
                if(ok)
                {
                    x[k] = i;
                    viz[i] = 1;
                    bkt(k+1);
                    viz[i] = 0;
                }
            }


        }
    }
    else
    {
        if(!gasit)
            afis();
        cnt++;
    }


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