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

#n = 4

pos = []
fpos = []
tcases = 0

def check(i, j):
    for p in pos:
        if i == p[0] or j == p[1]:
            return False
        if abs(i - p[0]) == abs(j - p[1]):
            return False
    return True


def back2(k = 0):
    global n
    global tcases
    if k == n:
        tcases += 1
        fpos.append(pos[:])
        return
    for j in range(0, n):
        if [k, j] not in pos and check(k, j):
            pos.append([k, j])
            back2(k+1)
            pos.pop()


back2()

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