import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Euler626 {
    static final long MOD = 1001001011L;

    static int v2(int x) {
        int c = 0;
        while ((x & 1) == 0) {
            x >>= 1;
            c++;
        }
        return c;
    }

    static class CycleType {
        int[] mult;
        List<Integer> valuations;
        BigInteger permCount;

        CycleType(int n) {
            mult = new int[n + 1];
            valuations = new ArrayList<>();
        }
    }

    static void buildCycleTypesRec(int n, int remaining, int minPart, List<Integer> current, BigInteger[] fact,
            List<CycleType> out) {
        if (remaining == 0) {
            CycleType t = new CycleType(n);
            for (int len : current) {
                t.mult[len]++;
                t.valuations.add(v2(len));
            }

            BigInteger denom = BigInteger.ONE;
            for (int len = 1; len <= n; len++) {
                int m = t.mult[len];
                if (m == 0)
                    continue;
                denom = denom.multiply(BigInteger.valueOf(len).pow(m));
                denom = denom.multiply(fact[m]);
            }
            t.permCount = fact[n].divide(denom);
            out.add(t);
            return;
        }

        for (int part = minPart; part <= remaining; part++) {
            current.add(part);
            buildCycleTypesRec(n, remaining - part, part, current, fact, out);
            current.remove(current.size() - 1);
        }
    }

    static List<CycleType> buildCycleTypes(int n, BigInteger[] fact) {
        List<CycleType> types = new ArrayList<>();
        buildCycleTypesRec(n, n, 1, new ArrayList<>(), fact, types);
        return types;
    }

    static class DSU {
        int[] parent;
        int[] rank;
        int[] forced;

        DSU(int n) {
            parent = new int[n];
            rank = new int[n];
            forced = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        int find(int x) {
            int r = x;
            while (parent[r] != r)
                r = parent[r];
            int curr = x;
            while (parent[curr] != curr) {
                int p = parent[curr];
                parent[curr] = r;
                curr = p;
            }
            return r;
        }

        void unite(int a, int b) {
            a = find(a);
            b = find(b);
            if (a == b)
                return;
            if (rank[a] < rank[b]) {
                int tmp = a;
                a = b;
                b = tmp;
            }
            parent[b] = a;
            forced[a] |= forced[b];
            if (rank[a] == rank[b])
                rank[a]++;
        }

        void setForced(int a) {
            int r = find(a);
            forced[r] = 1;
        }
    }

    static int parityRank(List<Integer> rowsV2, List<Integer> colsV2) {
        int r = rowsV2.size();
        int s = colsV2.size();
        int vars = r + s;
        DSU dsu = new DSU(vars);

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < s; j++) {
                if (rowsV2.get(i).equals(colsV2.get(j))) {
                    dsu.unite(i, r + j);
                } else if (rowsV2.get(i) > colsV2.get(j)) {
                    dsu.setForced(i);
                } else {
                    dsu.setForced(r + j);
                }
            }
        }

        int[] seen = new int[vars];
        int freeComponents = 0;
        for (int v = 0; v < vars; v++) {
            int root = dsu.find(v);
            if (seen[root] == 1)
                continue;
            seen[root] = 1;
            if (dsu.forced[root] == 0)
                freeComponents++;
        }
        return vars - freeComponents;
    }

    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static int orbitCount(CycleType a, CycleType b, int[][] gcdTbl, int n) {
        int o = 0;
        for (int p = 1; p <= n; p++) {
            int mp = a.mult[p];
            if (mp == 0)
                continue;
            for (int q = 1; q <= n; q++) {
                int mq = b.mult[q];
                if (mq == 0)
                    continue;
                o += mp * mq * gcdTbl[p][q];
            }
        }
        return o;
    }

    static BigInteger computeCExact(int n) {
        BigInteger[] fact = new BigInteger[n + 1];
        fact[0] = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1].multiply(BigInteger.valueOf(i));
        }

        List<CycleType> types = buildCycleTypes(n, fact);

        int[][] gcdTbl = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                gcdTbl[i][j] = gcd(i, j);
            }
        }

        BigInteger total = BigInteger.ZERO;
        int tcount = types.size();

        for (int i = 0; i < tcount; i++) {
            CycleType a = types.get(i);
            for (int j = 0; j < tcount; j++) {
                CycleType b = types.get(j);
                int o = orbitCount(a, b, gcdTbl, n);
                int rk = parityRank(a.valuations, b.valuations);
                int exp = o - rk;
                BigInteger term = a.permCount.multiply(b.permCount).multiply(BigInteger.valueOf(2).pow(exp));
                total = total.add(term);
            }
        }

        BigInteger denom = fact[n].multiply(fact[n]);
        return total.divide(denom);
    }

    public static String solve() {
        BigInteger c20 = computeCExact(20);
        return c20.remainder(BigInteger.valueOf(MOD)).toString();
    }

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