#include <fstream>
using namespace std;

ofstream cout("damesah.out");
ifstream cin("damesah.in");

int vf[40], x[40], n, ans = 0;

bool check(int pas){
    for(int i = 1;i<pas;i++){
        if(pas - i == abs(x[pas] - x[i]))return 0;
    }
    return 1;
}

void backtrack(int pas){
    if(pas == n + 1){
        ans++;
        if(ans == 1){
            for(int i = 1;i<=n;i++){
                cout << x[i] << ' ';
            }
            cout << '\n';
        }
    }else{
        for(int i= 1;i<=n;i++){
            if(vf[i] == 0){
                vf[i] = 1;
                x[pas] = i;
                if(check(pas)){
                    backtrack(pas+1);
                }
                vf[i] = 0;
            }
        }
    }
}

int main(void){
    cin >> n;
    backtrack(1);
    cout << ans;
}