#include <cstdio>
#include <cmath>

int main() {
    int n, k = 1, st[14], i, cnt = 0;
    bool as, ev;
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &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) {
                ++cnt;
                if(cnt == 1)
                    for(i = 1; i <= n; ++i)
                        printf("%d ", st[i]);
            }
            else
                st[++k] = 0;
        else
            --k;        
    }

    printf("\n%d", cnt);
}