f = open("damesah.in" , "r")
g = open("damesah.out" , "w")

n = (int) ( f.read() )

usu = [ [0] * n for i in range(n) ]

sol = [0] * n

nr = 0

viz = [0] * n

d1 = [0] * n * 5
d2 = [0] * n * 5

def solve (lin):
    global nr
    if lin == n:
        if nr == 0:
            for i in range(0,n):
                g.write(str(sol[i] + 1) + " ")
        nr += 1
        return

    for i in range(0,n):
        if viz[i] == 1:
            continue

        if d1[lin + i] == 1:
            continue

        if d2[i - lin + n + 1] == 1:
            continue

        sol[lin] = i

        viz[i] = 1

        d1[i + lin] = 1

        d2[i - lin + n + 1] = 1

        solve(lin + 1)

        viz[i] = 0

        d1[i + lin] = 0

        d2[i - lin + n + 1] = 0


solve(0)
g.write("\n")
g.write(str(nr))