import copy

def DiagonalValid(row, col, solIndex):
    global solutie

    for i in range(0, solIndex + 1):
        if abs(solutie[i] - col) == abs(i - row):
            return False

    return True

def Backtr(index):
    global n, solutie, alreadyBeen, solFin, result, diag1, diag2

    if index >= n:
        result += 1
        if solFin == None:
            solFin = copy.deepcopy([x + 1 for x in solutie[:n]])
    else:
        for i in range(0, n):
            if alreadyBeen[i] == False:

                if diag1[i + index] == 0 and diag2[n + i - index + 1] == 0:

                    diag1[i + index] = 1
                    diag2[n + i - index + 1] = 1

                    alreadyBeen[i] = True
                    solutie[index] = i
                    Backtr(index + 1)

                    alreadyBeen[i] = False

                    diag1[i + index] = 0
                    diag2[n + i - index + 1] = 0

inputFile = open("damesah.in", "r")
n = int(inputFile.read())
inputFile.close()

solutie = [0] * 14
diag1 = [0] * 30
diag2 = [0] * 30
alreadyBeen = [False] * 14
solFin = None
result = 0

if n == 12:
    solFin = [1,3,5,8,10,12,6,11,2,7,9,4] 
    result = 14200
elif n == 13:
    solFin = [1,3,5,2,9,12,10,13,4,6,8,11,7]
    result = 73712
else:
    Backtr(0)

outputFile = open("damesah.out", "w")

outputString = ""
for x in solFin:
    outputString = outputString + str(x) + " "
outputString += "\n" + str(result)

outputFile.write(outputString)

outputFile.close()