#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector<int> v;
int cnt = 0;

bool isValid() {
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (j - i == abs(v[j] - v[i])) {
                return false;
            }
        }
    }
    return true;
}

int main(int argc, const char * argv[]) {
    ifstream cin("damesah.in");
    ofstream cout("damesah.out");
    
    cin >> n;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        v[i] = i;
    }
    
    do {
        if (isValid()) {
            cnt++;
            
            if (cnt == 1) {
                for (int i = 1; i <= n; i++) {
                    cout << v[i] << ' ';
                }
                cout << '\n';
            }
        }
    } while (next_permutation(v.begin() + 1, v.end()));
    
    cout << cnt;
    
    return 0;
}