#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define INFILE "damesah.in"
#define OUTFILE "damesah.out"

const int VMAX = 14;

int v[VMAX];
int solution[VMAX];

void printSolution(int number){

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

        solution[i] = v[i];

    }

}

bool verify(int k){

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

        if((v[k] == v[i]) || (k - i == abs(v[k] - v[i]))){

            return false;

        }

    }

    return true;

}

int back(int number){

    int isSolution, count = 0, k = 1, first = 1;

    v[k] = 0;

    while(k > 0){

        isSolution = 0;

        while(v[k] < number && (!isSolution)){

            ++v[k];
            isSolution = verify(k);

        }

        if(!isSolution){

            --k;
            
        }
        else{

            if(k == number){

                if(first){

                    printSolution(number);

                    first = 0;

                }

                ++count;

            }
            else{

                ++k;

                v[k] = 0;

            }

        }

    }

    return count;

}

void solve(){

    int n;
    cin >> n;

    int count = back(n);

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

        cout << solution[i] << " ";

    }

    cout << '\n';

    cout << count << '\n';

}

int main(){
    
    ios_base::sync_with_stdio(false);

    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);

    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}