f = open('damesah.in', 'r')
g = open('damesah.out', 'w')
n = int(f.read())

d1 = [0] * 20
d2 = [0] * 20
col = [0] * 20
flag = False
v = [0] * 20
total = 0

def back(row):
    global flag
    global v
    global total
    if (row == n):
        if flag == False:
            flag = True
            for i in range(n):
                g.write(str(v[i] + 1) + ' ')
        total += 1
    for i in range(n):
        if (col[i] or d2[i + row] or d1[row - i + n]):
            continue
        col[i] = d2[i + row] = d1[row - i + n] = 1
        v[row] = i
        back(row + 1)
        col[i] = d2[i + row] = d1[row - i + n] = 0

back(0)
g.write('\n' + str(total))
f.close()
g.close()