#include<bits/stdc++.h>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int N, Sol[30], Main_Diag[30], Sec_Diag[30], Ans;
bool ok = false, F[30];

void solve( int k ){

    if( k == N + 1 ){

        Ans++;

        if( ok == false ){

            ok = true;
            for( int i = 1; i <= N; i++ )
                fout << Sol[i] << " ";
            fout << "\n";

        }

    }else{

        for( int i = 1; i <= N; i++ ){

            if( F[i] == true )
                continue;

            int m_diag, s_diag;

            m_diag = N - (i - k);
            s_diag = i + k - 1;

            if( Main_Diag[m_diag] == false && Sec_Diag[s_diag] == false ){

                Main_Diag[m_diag] = true, Sec_Diag[s_diag] = true;
                Sol[k] = i;
                F[i] = true;

                solve( k + 1 );

                F[i] = false;
                Sol[k] = 0;
                Main_Diag[m_diag] = false, Sec_Diag[s_diag] = false;

            }

        }

    }

}

int main(){

    fin >> N;

    memset( F, false, sizeof(F) );
    solve( 1 );

    fout << Ans << "\n";

    return 0;
}