#!/usr/bin/env python3

import sys
sys.stdout = open('damesah.out', 'w')

with open('damesah.in', 'r') as f:
    N = int(next(line for line in f if line.strip()))

    v, d1, d2, sol, num, first = [False] * N, [False] * N * 2, [False] * N * 2, [0] * N, 0, None
    
    def solve(i, c):
        global first
        if not first: sol[i] = c

        if i == N - 1:
            if not first: first = ' '.join(str(x + 1) for x in sol)
            return 1
        else:
            v[c] = d1[i-c] = d2[2*N-i-c-1] = True
            cnt = sum(solve(i + 1, c) for c in range(N) if not v[c] and not d1[i+1-c] and not d2[2*N-i-c-2])
            v[c] = d1[i-c] = d2[2*N-i-c-1] = False
            return cnt

    cnt = sum(solve(0, c) for c in range(N))
    
    print(first)
    print(cnt)