def write():
    global n, cnt
    if cnt == 1:
        with open("damesah.out", "w") as fout:
            for i in range(1, n + 1):
                print(st[i], end=" ", file=fout)
            print(file=fout)
    cnt += 1


def back(top):
    global n
    if top > n:
        write()
    for i in range(1, n + 1):
        if freq[i] == 0 and True not in [abs(i - st[j]) == abs(top - j) for j in range(1, top)]:
            st[top] = i
            freq[i] = 1
            back(top + 1)
            freq[i] = 0


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


if __name__ == '__main__':
    read()
    freq = [0] * (n + 1)
    st = [0] * (n + 1)
    cnt = 1
    back(1)
    with open("damesah.out", "a") as fout:
        print(cnt - 1, file=fout)