def input_gen_int(fnmae):
    with open(fnmae, 'rt') as fin:
        for line in fin:
            for val in line.split():
                yield int(val)


class Chess_queen:
    row = []
    main_diag = []
    anti_diag = []
    colpos = []
    foundsol = 0
    solnum = 0
    n = 0

    def __init__(self, n):
        self.n = n;
        self.row = [0 for _ in range(n)]
        self.main_diag = [0 for _ in range(2 * n)]
        self.anti_diag = [0 for _ in range(2 * n)]
        self.colpos = [0 for _ in range(n)]

    def generate(self, k):
        for i in range(n):
            if self.row[i] == 0 and self.main_diag[i + k] == 0 and self.anti_diag[i - k + n] == 0:
                self.row[i] = 1;
                self.main_diag[i + k] = 1;
                self.anti_diag[i - k + n] = 1;

                self.colpos[k] = i;
                if k != n - 1:
                    self.generate(k + 1)
                else:
                    self.solnum = self.solnum + 1
                    if not self.foundsol:
                        self.foundsol = 1
                        self.sol = self.colpos.copy()

                self.row[i] = 0;
                self.main_diag[i + k] = 0;
                self.anti_diag[i - k + n] = 0;

    def getNumofSol(self):
        return self.solnum

    def getFirstSolVec(self):
        return self.sol


if __name__ == "__main__":
    ig = input_gen_int("damesah.in")
    n = next(ig)
    chq = Chess_queen(n)
    chq.generate(0)

    with open("damesah.out", 'wt') as fout:
        for i in chq.getFirstSolVec():
            fout.write('{} '.format(i + 1))
        fout.write('\n{}'.format(chq.getNumofSol()))