#include <fstream>
using namespace std;
 
ifstream cin ("damesah.in");
ofstream cout ("damesah.out");
 
int n, ans;
int x[100], l[100], d1[100], d2[100];
 
void afisare () {
    for(int i = 1; i <= n; ++i)
        cout << x[i] << " ";
    cout << '\n';
}
 
void bk (int k) {
    for(int i = 1; i <= n; ++i) {
        if(l[i] == 0 && d1[i - k + n] == 0 && d2[k + i] == 0) {
            x[k] = i;
            l[i] = d1[i - k + n] = d2[k + i] = 1;
            if(k == n) {
                ans += 1;
                if(ans == 1) afisare();
            }
            else bk(k+1);
            l[i] = d1[i - k + n] = d2[k + i] = 0;
        }
    }
}
 
int main()
{
    cin >> n;
 
    bk(1);
    cout << ans;
    return 0;
}