#include <fstream>
 
int abs(int x) {
    return x < 0 ? -x : x;
}
 
int main() {
    int n, k = 1, st[15], i, cnt = 0;
    bool as, ev;
    std::ifstream fin("damesah.in");
    std::ofstream fout("damesah.out");
    fin >> n;
    while(k) {
        do {
            as = 0;
            if(st[k] < n) {
                ++st[k];
                as = 1;
            }
            if(as) {
                ev = 1;
                for(i = 1; i < k; ++i)
                    if(k - i == abs(st[k] - st[i]) || st[i] == st[k])
                        ev = 0;
            }
        } while(as && !ev);
        if(as)
            if(k == n) {
                if(cnt == 0)
                    for(i = 1; i <= n; ++i)
                        fout << st[i] << ' ';
                ++cnt;
         	}            		
            else
                st[++k] = 0;
        else
            --k;        
    }
    fout << '\n' << cnt << '\n';
}