def backtracking(k):
    global ans, dame, n, col, dp, ds
    if k == n + 1:
        if ans == 0:
            afiseaza()
        ans += 1
        return
    for i in range(1, n + 1):

        if col[i] == True or dp[n - i + 1 + k] == True or ds[i + k] == True:
            continue

        dame[k] = i
        col[i] = dp[n - i + 1 + k] = ds[i + k] = True

        backtracking(k + 1)
        col[i] = dp[n - i + 1 + k] = ds[i + k] = False


def afiseaza():
    global dame, n
    for i in range(1, n + 1):
        #print(dame[i], end=' ')
        print(dame[i], end = ' ', file = f)
    #print("")
    print('', file = f)

with open('damesah.in') as f:
    try:
        n = int(f.readline())
    except ValueError:
        n = int(f.readline())

#n = int(input())

ans = 0
dame = [0] * (n + 1)
col = [False] * (n + 1)
dp = [False] * 50
ds = [False] * 50

with open('damesah.out', 'w') as f:
    backtracking(1)
    #print(ans)
    print(ans, file = f)