import java.util.*;

public class Euler886 {
    static final int MOD = 83456729;

    static int addMod(int a, int b) {
        int s = a + b;
        if (s >= MOD)
            s -= MOD;
        return s;
    }

    static int subMod(int a, int b) {
        int s = a - b;
        if (s < 0)
            s += MOD;
        return s;
    }

    static int mulMod(long a, long b) {
        return (int) ((a * b) % MOD);
    }

    static int modPow(int a, long e) {
        long r = 1;
        long x = a % MOD;
        if (x < 0)
            x += MOD;
        while (e > 0) {
            if ((e & 1) == 1)
                r = (r * x) % MOD;
            x = (x * x) % MOD;
            e >>= 1;
        }
        return (int) r;
    }

    static int modInv(int a) {
        return modPow(a, MOD - 2);
    }

    static int[][] buildBinom(int n) {
        int[][] C = new int[n + 1][];
        C[0] = new int[] { 1 };
        for (int i = 1; i <= n; ++i) {
            C[i] = new int[i + 1];
            Arrays.fill(C[i], 1);
            for (int j = 1; j < i; ++j) {
                C[i][j] = addMod(C[i - 1][j - 1], C[i - 1][j]);
            }
        }
        return C;
    }

    static int determinantMod(int[][] origA) {
        int n = origA.length;
        if (n == 0)
            return 1;
        if (n == 1)
            return origA[0][0] % MOD;

        int[][] A = new int[n][n];
        for (int i = 0; i < n; i++)
            A[i] = origA[i].clone();

        int resultInverse = 1;

        for (int i = 0; i < n - 2; ++i) {
            int rowToUse = -1;
            for (int r = i; r < n; ++r) {
                if (A[r][i] % MOD != 0) {
                    rowToUse = r;
                    break;
                }
            }
            if (rowToUse < 0)
                return 0;

            if (i != rowToUse) {
                int[] temp = A[rowToUse];
                A[rowToUse] = A[i];
                A[i] = temp;
                resultInverse = (resultInverse == 0) ? 0 : MOD - resultInverse;
            }

            int Aii = A[i][i] % MOD;
            resultInverse = mulMod(resultInverse, modPow(Aii, n - i - 2));

            for (int r = i + 1; r < n; ++r) {
                int x = A[r][i] % MOD;
                A[r][i] = 0;
                for (int c = i + 1; c < n; ++c) {
                    int v = subMod(mulMod(Aii, A[r][c]), mulMod(x, A[i][c]));
                    A[r][c] = v;
                }
            }
        }

        int last = subMod(mulMod(A[n - 2][n - 2], A[n - 1][n - 1]),
                mulMod(A[n - 2][n - 1], A[n - 1][n - 2]));
        return mulMod(last, modInv(resultInverse));
    }

    static int permanentModWithColumnClasses(int[][] A, int[][] binom) {
        int n = A.length;
        if (n == 0)
            return 1;

        Map<Long, List<Integer>> columnClasses = new HashMap<>();
        for (int col = 0; col < n; ++col) {
            long mask = 0;
            for (int r = 0; r < n; ++r) {
                if (A[r][col] != 0)
                    mask |= (1L << r);
            }
            columnClasses.computeIfAbsent(mask, k -> new ArrayList<>()).add(col);
        }

        List<List<Integer>> classes = new ArrayList<>();
        for (List<Integer> inds : columnClasses.values()) {
            if (inds.size() >= 3) {
                classes.add(inds);
            } else {
                for (int idx : inds) {
                    List<Integer> single = new ArrayList<>();
                    single.add(idx);
                    classes.add(single);
                }
            }
        }
        classes.sort(Comparator.comparingInt(List::size));

        int[] newColOrder = new int[n];
        int colIdx = 0;
        for (List<Integer> c : classes) {
            for (int idx : c)
                newColOrder[colIdx++] = idx;
        }

        int[][] B = new int[n][n];
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                B[r][c] = A[r][newColOrder[c]];
            }
        }

        int[] classSizes = new int[classes.size()];
        for (int i = 0; i < classes.size(); i++)
            classSizes[i] = classes.get(i).size();

        int defaultBlockExponent = 10;
        int smallestClassCount = 0;
        int smallestClassIndexCount = 0;
        while (smallestClassCount < classSizes.length &&
                smallestClassIndexCount + classSizes[smallestClassCount] < defaultBlockExponent) {
            smallestClassIndexCount += classSizes[smallestClassCount];
            ++smallestClassCount;
        }

        int blockExponent = smallestClassIndexCount;
        int blockSize = 1 << blockExponent;

        int numHighClasses = classSizes.length - smallestClassCount;
        int[] highClassSizes = new int[numHighClasses];
        int[] highClassOffsets = new int[numHighClasses];
        int off = blockExponent;
        for (int i = 0; i < numHighClasses; ++i) {
            highClassSizes[i] = classSizes[smallestClassCount + i];
            highClassOffsets[i] = off;
            off += highClassSizes[i];
        }

        int[] resultBlock = new int[blockSize];
        int[] highMask = new int[n];

        int[] popcnt = new int[blockSize];
        for (int s = 1; s < blockSize; ++s)
            popcnt[s] = popcnt[s >> 1] + (s & 1);

        rec(0, 1, 0, highClassSizes, highClassOffsets, blockExponent, blockSize, n, B, binom, highMask, popcnt,
                resultBlock);

        int result = 0;
        for (int v : resultBlock) {
            result = addMod(result, v);
        }
        if ((n & 1) != 0) {
            result = (result == 0) ? 0 : (MOD - result);
        }
        return result;
    }

    static void rec(int clsIdx, int totalWays, int highOnes, int[] highClassSizes, int[] highClassOffsets,
            int blockExponent, int blockSize, int n, int[][] B, int[][] binom, int[] highMask, int[] popcnt,
            int[] resultBlock) {
        if (clsIdx == highClassSizes.length) {
            for (int state = 0; state < blockSize; ++state) {
                int term = totalWays;
                for (int r = 0; r < n; ++r) {
                    int sum = 0;
                    for (int c = 0; c < blockExponent; ++c) {
                        if (((state >> c) & 1) != 0)
                            sum += B[r][c];
                    }
                    for (int c = blockExponent; c < n; ++c) {
                        if (highMask[c] != 0)
                            sum += B[r][c];
                    }
                    term = mulMod(term, sum);
                    if (term == 0)
                        break;
                }

                if (((popcnt[state] + highOnes) & 1) != 0 && term != 0) {
                    term = MOD - term;
                }
                resultBlock[state] = addMod(resultBlock[state], term);
            }
            return;
        }

        int sz = highClassSizes[clsIdx];
        int base = highClassOffsets[clsIdx];

        for (int ones = 0; ones <= sz; ++ones) {
            for (int j = 0; j < sz; ++j) {
                highMask[base + j] = (j >= sz - ones) ? 1 : 0;
            }
            int ways2 = mulMod(totalWays, binom[sz][ones]);
            rec(clsIdx + 1, ways2, highOnes + ones, highClassSizes, highClassOffsets, blockExponent, blockSize, n, B,
                    binom, highMask, popcnt, resultBlock);
        }
    }

    static class RowClass {
        int idx;
        int size;

        RowClass(int idx, int size) {
            this.idx = idx;
            this.size = size;
        }
    }

    static List<RowClass> rowClasses(int[][] A) {
        Map<Long, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < A.length; ++i) {
            long mask = 0;
            for (int j = 0; j < A[i].length; ++j) {
                if (A[i][j] != 0)
                    mask |= (1L << j);
            }
            groups.computeIfAbsent(mask, k -> new ArrayList<>()).add(i);
        }

        List<RowClass> out = new ArrayList<>();
        for (List<Integer> idxs : groups.values()) {
            out.add(new RowClass(idxs.get(0), idxs.size()));
        }
        return out;
    }

    interface CombCallback {
        void call(int[] comb);
    }

    static void forEachCombination(int n, int k, CombCallback fn) {
        if (k < 0 || k > n)
            return;
        if (k == 0) {
            fn.call(new int[0]);
            return;
        }
        int[] comb = new int[k];
        for (int i = 0; i < k; ++i)
            comb[i] = i;

        while (true) {
            fn.call(comb);
            int i = k - 1;
            while (i >= 0 && comb[i] == n - k + i)
                --i;
            if (i < 0)
                break;
            ++comb[i];
            for (int j = i + 1; j < k; ++j) {
                comb[j] = comb[j - 1] + 1;
            }
        }
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static int PMod(int n) {
        int halfN = n / 2;

        int[] evenIndices = new int[halfN];
        int[] oddIndices = new int[halfN];
        int evenIdx = 0, oddIdx = 0;
        for (int x = 1; x < n; x += 2)
            evenIndices[evenIdx++] = x;
        for (int x = 2; x <= n; x += 2)
            oddIndices[oddIdx++] = x;

        int[][] B = new int[halfN][halfN];
        for (int c = 0; c < halfN; ++c) {
            for (int r = 0; r < halfN; ++r) {
                B[c][r] = (gcd(evenIndices[r], oddIndices[c]) == 1) ? 1 : 0;
            }
        }

        int[][] binom = buildBinom(halfN);

        List<RowClass> rowsAndWays = rowClasses(B);
        if (!rowsAndWays.isEmpty()) {
            int rowToRemove = -1;
            for (int i = 0; i < rowsAndWays.size(); ++i) {
                if (rowsAndWays.get(i).size == 1) {
                    rowToRemove = i;
                    break;
                }
            }
            if (rowToRemove >= 0) {
                rowsAndWays.remove(rowToRemove);
            } else {
                rowsAndWays.get(0).size -= 1;
            }
        }

        int[][] BT = new int[halfN][halfN];
        for (int r = 0; r < halfN; ++r) {
            for (int c = 0; c < halfN; ++c) {
                BT[r][c] = B[c][r];
            }
        }
        List<RowClass> colsAndWays = rowClasses(BT);

        int[] result = { 0 };

        for (int included = 0; included < halfN; ++included) {
            final int inc = included;
            forEachCombination(rowsAndWays.size(), included, rowsPick -> {
                long rowsWays = 1;
                int[] includedRows = new int[inc];
                for (int i = 0; i < inc; i++) {
                    RowClass rc = rowsAndWays.get(rowsPick[i]);
                    rowsWays = (rowsWays * rc.size) % MOD;
                    includedRows[i] = rc.idx;
                }

                boolean[] inRow = new boolean[halfN];
                for (int r : includedRows)
                    inRow[r] = true;
                int[] notRows = new int[halfN - inc];
                int notRowIdx = 0;
                for (int r = 0; r < halfN; ++r) {
                    if (!inRow[r])
                        notRows[notRowIdx++] = r;
                }

                final long finalRowsWays = rowsWays;
                forEachCombination(colsAndWays.size(), inc, colsPick -> {
                    long ways = finalRowsWays;
                    int[] includedCols = new int[inc];
                    for (int i = 0; i < inc; i++) {
                        RowClass cc = colsAndWays.get(colsPick[i]);
                        ways = (ways * cc.size) % MOD;
                        includedCols[i] = cc.idx;
                    }

                    int[][] detMat = new int[inc][inc];
                    for (int i = 0; i < inc; ++i) {
                        for (int j = 0; j < inc; ++j) {
                            detMat[i][j] = B[includedRows[i]][includedCols[j]];
                        }
                    }

                    int detVal = determinantMod(detMat);
                    if (detVal == 0)
                        return;

                    detVal = mulMod(detVal, detVal);
                    if ((inc & 1) != 0) {
                        detVal = (detVal == 0) ? 0 : (MOD - detVal);
                    }

                    boolean[] inCol = new boolean[halfN];
                    for (int c : includedCols)
                        inCol[c] = true;
                    int[] notCols = new int[halfN - inc];
                    int notColIdx = 0;
                    for (int c = 0; c < halfN; ++c) {
                        if (!inCol[c])
                            notCols[notColIdx++] = c;
                    }

                    int rest = halfN - inc;
                    int[][] perMat = new int[rest][rest];
                    for (int i = 0; i < rest; ++i) {
                        for (int j = 0; j < rest; ++j) {
                            perMat[i][j] = B[notRows[i]][notCols[j]];
                        }
                    }

                    int perVal = permanentModWithColumnClasses(perMat, binom);
                    perVal = mulMod(perVal, perVal);

                    int term = mulMod(ways, mulMod(detVal, perVal));
                    result[0] = addMod(result[0], term);
                });
            });
        }

        return result[0];
    }

    public static String solve() {
        return Integer.toString(PMod(34));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}