first_ans = False
with open("damesah.in", "r") as r:
    n = int(r.read())
M = [[None for i in range(0, n)] for j in range(0,n)]
Rez = []

def verif():
    L = []
    for i in range(0, n):
        for j in range(0, n):
            if M[i][j] == 1:
                newDama = [i, j]
                for dama in L:
                    if dama[0] == newDama[0] or dama[1] == newDama[1]:
                        return 0
                    if abs(dama[0] - newDama[0]) == abs(dama[1] - newDama[1]):
                        return 0

                L += [newDama]

    if(len(L) == n):
        global first_ans
        if not first_ans:
            global Rez
            for dama in L:
                Rez.append(dama[1] + 1)
            first_ans = True
            print('')
        return 1

    return 0


def back(i, j, nrDame):
    if nrDame == n:
        return verif()
    if j == n:
        return back(i+1, 0, nrDame)
    if i == n:
        return 0
    M[i][j] = 1
    X = back(i+1, 0, nrDame+1)
    M[i][j] = 0
    X += back(i, j + 1, nrDame)
    return X


nr = back(0, 0, 0)

with open("damesah.out", "w") as w:
    for d in Rez:
        w.write(str(d))
        w.write(' ')
    w.write('\n')
    w.write(str(nr))