with open("damesah.in", "r") as r:
    n = int(r.read())

#n = 4

pos = []
fpos = []
tcases = 0

diag1 = []
diag2 = []

ttw = ""

def check(i, j):
    if j in pos:
        return False
    if i + j in diag1 or i - j in diag2:
        return False
    return True

def back(i = 0):
    global n
    global tcases
    if i == n:
        tcases += 1
        fpos.append(pos[:])
        return
    for j in range(0, n):
        if check(i, j):
            pos.append(j)
            diag1.append(i + j)
            diag2.append(i - j)
            back(i + 1)
            pos.pop()
            diag1.pop()
            diag2.pop()

'''
for n in range(4, 14):
    back()
    tw = fpos[0][:]
    for p in tw:
        ttw += str(p + 1) + " "
    ttw += '\n' + str(tcases) + '\n'
    fpos.clear()
    tcases = 0

with open("damesah.out", "w") as w:
    w.write(ttw)
'''

back()

with open("damesah.out", "w") as w:
    tw = fpos[0][:]
    for p in tw:
        ttw += str(p + 1) + " "
    ttw += '\n' + str(tcases)
    w.write(ttw)