import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Euler673 {

    static final long MOD = 999999937L;

    static class Pair {
        int first, second;

        Pair(int f, int s) {
            first = f;
            second = s;
        }
    }

    static class Comp {
        int[] b, d;

        Comp(int[] b, int[] d) {
            this.b = b;
            this.d = d;
        }
    }

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

    static List<Pair> parsePairs(String data) {
        List<Pair> out = new ArrayList<>();
        String[] lines = data.split("\n");
        for (String line : lines) {
            line = line.trim();
            if (line.isEmpty())
                continue;
            int pos = line.indexOf(',');
            int a = Integer.parseInt(line.substring(0, pos));
            int b = Integer.parseInt(line.substring(pos + 1));
            out.add(new Pair(a, b));
        }
        return out;
    }

    static List<Comp> buildComponents(int n, List<Pair> beds, List<Pair> desks) {
        int[] b = new int[n + 1];
        int[] d = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            b[i] = i;
            d[i] = i;
        }

        for (Pair p : beds) {
            b[p.first] = p.second;
            b[p.second] = p.first;
        }
        for (Pair p : desks) {
            d[p.first] = p.second;
            d[p.second] = p.first;
        }

        boolean[] seen = new boolean[n + 1];
        int[] loc = new int[n + 1];
        for (int i = 0; i <= n; i++)
            loc[i] = -1;

        List<Comp> comps = new ArrayList<>();

        for (int s = 1; s <= n; ++s) {
            if (seen[s])
                continue;

            Stack<Integer> stack = new Stack<>();
            stack.push(s);
            seen[s] = true;
            List<Integer> verts = new ArrayList<>();

            while (!stack.isEmpty()) {
                int v = stack.pop();
                verts.add(v);

                int nb = b[v];
                int nd = d[v];
                if (!seen[nb]) {
                    seen[nb] = true;
                    stack.push(nb);
                }
                if (!seen[nd]) {
                    seen[nd] = true;
                    stack.push(nd);
                }
            }

            for (int i = 0; i < verts.size(); ++i) {
                loc[verts.get(i)] = i;
            }

            int[] cb = new int[verts.size()];
            int[] cd = new int[verts.size()];
            for (int i = 0; i < verts.size(); ++i) {
                int v = verts.get(i);
                cb[i] = loc[b[v]];
                cd[i] = loc[d[v]];
            }

            for (int v : verts) {
                loc[v] = -1;
            }

            comps.add(new Comp(cb, cd));
        }
        return comps;
    }

    static class Matcher {
        Comp a, b;
        int[] mapA, mapB;
        Stack<Integer> stack;
        int assigned;

        Matcher(Comp a, Comp b) {
            this.a = a;
            this.b = b;
            int m = a.b.length;
            mapA = new int[m];
            mapB = new int[m];
            for (int i = 0; i < m; i++) {
                mapA[i] = -1;
                mapB[i] = -1;
            }
            stack = new Stack<>();
        }

        boolean step(int nx, int ny) {
            int cur = mapA[nx];
            if (cur == -1) {
                if (mapB[ny] != -1)
                    return false;
                mapA[nx] = ny;
                mapB[ny] = nx;
                stack.push(nx);
                assigned++;
                return true;
            }
            return cur == ny;
        }

        boolean tryMapRoot(int startB) {
            mapA[0] = startB;
            mapB[startB] = 0;
            stack.push(0);
            assigned = 1;

            while (!stack.isEmpty()) {
                int x = stack.pop();
                int y = mapA[x];

                int nxB = a.b[x];
                int nyB = b.b[y];
                if (!step(nxB, nyB))
                    return false;

                int nxD = a.d[x];
                int nyD = b.d[y];
                if (!step(nxD, nyD))
                    return false;
            }

            return assigned == a.b.length;
        }
    }

    static boolean tryMapRootWrapper(Comp a, Comp b, int startB) {
        return new Matcher(a, b).tryMapRoot(startB);
    }

    static int isomorphismCount(Comp a, Comp b) {
        if (a.b.length != b.b.length)
            return 0;
        int m = b.b.length;
        int count = 0;
        for (int s = 0; s < m; ++s) {
            if ((a.b[0] == 0) != (b.b[s] == s))
                continue;
            if ((a.d[0] == 0) != (b.d[s] == s))
                continue;
            if (tryMapRootWrapper(a, b, s))
                count++;
        }
        return count;
    }

    static long countValidPermutations(int n, List<Pair> beds, List<Pair> desks) {
        List<Comp> comps = buildComponents(n, beds, desks);
        int c = comps.size();
        boolean[] used = new boolean[c];
        long ans = 1;

        for (int i = 0; i < c; ++i) {
            if (used[i])
                continue;
            used[i] = true;
            int aut = isomorphismCount(comps.get(i), comps.get(i));

            int mult = 1;
            for (int j = i + 1; j < c; ++j) {
                if (used[j])
                    continue;
                if (isomorphismCount(comps.get(i), comps.get(j)) > 0) {
                    used[j] = true;
                    mult++;
                }
            }

            long fac = 1;
            for (int t = 2; t <= mult; ++t) {
                fac = (fac * t) % MOD;
            }

            ans = (ans * modPow(aut, mult)) % MOD;
            ans = (ans * fac) % MOD;
        }
        return ans;
    }

    static final String BEDS_500 = "1,352\n" +
            "2,251\n" +
            "3,243\n" +
            "4,311\n" +
            "5,312\n" +
            "6,231\n" +
            "7,416\n" +
            "8,166\n" +
            "9,384\n" +
            "10,330\n" +
            "11,89\n" +
            "12,316\n" +
            "13,394\n" +
            "14,57\n" +
            "15,177\n" +
            "16,341\n" +
            "17,149\n" +
            "18,199\n" +
            "19,310\n" +
            "20,421\n" +
            "21,459\n" +
            "22,189\n" +
            "23,308\n" +
            "25,46\n" +
            "26,460\n" +
            "27,63\n" +
            "28,34\n" +
            "29,295\n" +
            "30,412\n" +
            "31,49\n" +
            "32,247\n" +
            "33,326\n" +
            "35,429\n" +
            "36,211\n" +
            "37,104\n" +
            "38,376\n" +
            "39,263\n" +
            "40,187\n" +
            "41,500\n" +
            "42,161\n" +
            "43,407\n" +
            "44,60\n" +
            "45,118\n" +
            "47,85\n" +
            "48,56\n" +
            "50,403\n" +
            "51,239\n" +
            "52,415\n" +
            "53,444\n" +
            "54,246\n" +
            "55,288\n" +
            "58,410\n" +
            "59,432\n" +
            "61,160\n" +
            "62,438\n" +
            "65,225\n" +
            "67,392\n" +
            "68,333\n" +
            "69,478\n" +
            "70,365\n" +
            "71,213\n" +
            "72,294\n" +
            "73,360\n" +
            "74,499\n" +
            "75,267\n" +
            "76,493\n" +
            "77,108\n" +
            "78,428\n" +
            "79,440\n" +
            "80,116\n" +
            "81,117\n" +
            "82,257\n" +
            "83,306\n" +
            "84,195\n" +
            "86,216\n" +
            "87,226\n" +
            "88,151\n" +
            "90,172\n" +
            "91,355\n" +
            "93,237\n" +
            "94,156\n" +
            "95,147\n" +
            "96,343\n" +
            "97,424\n" +
            "98,112\n" +
            "100,240\n" +
            "101,163\n" +
            "102,371\n" +
            "103,361\n" +
            "106,315\n" +
            "107,230\n" +
            "109,227\n" +
            "110,336\n" +
            "111,377\n" +
            "113,253\n" +
            "114,367\n" +
            "115,139\n" +
            "119,290\n" +
            "120,121\n" +
            "122,174\n" +
            "123,159\n" +
            "124,282\n" +
            "125,142\n" +
            "126,435\n" +
            "127,452\n" +
            "128,338\n" +
            "129,445\n" +
            "130,448\n" +
            "131,183\n" +
            "132,179\n" +
            "133,196\n" +
            "134,268\n" +
            "135,170\n" +
            "136,357\n" +
            "137,368\n" +
            "138,242\n" +
            "141,400\n" +
            "143,278\n" +
            "144,208\n" +
            "145,204\n" +
            "146,378\n" +
            "148,252\n" +
            "152,238\n" +
            "153,380\n" +
            "154,269\n" +
            "155,270\n" +
            "157,373\n" +
            "158,339\n" +
            "162,272\n" +
            "164,332\n" +
            "167,466\n" +
            "168,327\n" +
            "169,266\n" +
            "173,471\n" +
            "175,494\n" +
            "176,463\n" +
            "178,433\n" +
            "180,198\n" +
            "181,258\n" +
            "182,464\n" +
            "184,467\n" +
            "186,409\n" +
            "188,191\n" +
            "190,346\n" +
            "192,446\n" +
            "193,418\n" +
            "197,474\n" +
            "200,354\n" +
            "201,479\n" +
            "202,436\n" +
            "205,404\n" +
            "206,475\n" +
            "207,349\n" +
            "210,476\n" +
            "212,372\n" +
            "214,379\n" +
            "217,232\n" +
            "218,320\n" +
            "219,366\n" +
            "220,356\n" +
            "221,299\n" +
            "222,426\n" +
            "223,484\n" +
            "224,264\n" +
            "228,359\n" +
            "229,405\n" +
            "233,483\n" +
            "234,391\n" +
            "235,381\n" +
            "236,262\n" +
            "241,420\n" +
            "244,393\n" +
            "245,337\n" +
            "248,296\n" +
            "249,370\n" +
            "250,325\n" +
            "254,351\n" +
            "255,302\n" +
            "256,364\n" +
            "260,431\n" +
            "261,447\n" +
            "265,318\n" +
            "271,397\n" +
            "273,375\n" +
            "274,469\n" +
            "275,453\n" +
            "276,328\n" +
            "279,313\n" +
            "280,292\n" +
            "283,434\n" +
            "284,495\n" +
            "285,386\n" +
            "286,454\n" +
            "287,385\n" +
            "289,363\n" +
            "291,304\n" +
            "293,382\n" +
            "297,389\n" +
            "298,383\n" +
            "301,461\n" +
            "303,347\n" +
            "305,369\n" +
            "309,439\n" +
            "314,344\n" +
            "317,491\n" +
            "319,443\n" +
            "321,470\n" +
            "322,437\n" +
            "323,411\n" +
            "324,406\n" +
            "331,340\n" +
            "334,358\n" +
            "335,456\n" +
            "342,414\n" +
            "345,396\n" +
            "350,390\n" +
            "374,408\n" +
            "387,422\n" +
            "395,487\n" +
            "398,423\n" +
            "399,485\n" +
            "401,441\n" +
            "402,473\n" +
            "413,457\n" +
            "417,449\n" +
            "425,451\n" +
            "427,477\n" +
            "430,496\n" +
            "442,488\n" +
            "450,480\n" +
            "462,490\n" +
            "465,482\n" +
            "472,492\n" +
            "481,486\n" +
            "497,498";

    static final String DESKS_500 = "1,106\n" +
            "2,429\n" +
            "4,94\n" +
            "6,349\n" +
            "7,362\n" +
            "8,100\n" +
            "9,368\n" +
            "10,477\n" +
            "11,132\n" +
            "12,328\n" +
            "13,319\n" +
            "14,185\n" +
            "15,225\n" +
            "16,279\n" +
            "17,72\n" +
            "18,51\n" +
            "19,482\n" +
            "20,270\n" +
            "21,50\n" +
            "22,449\n" +
            "23,398\n" +
            "24,492\n" +
            "25,478\n" +
            "26,360\n" +
            "27,428\n" +
            "28,240\n" +
            "29,103\n" +
            "30,32\n" +
            "31,484\n" +
            "33,296\n" +
            "34,371\n" +
            "35,251\n" +
            "36,444\n" +
            "37,460\n" +
            "38,491\n" +
            "39,180\n" +
            "40,264\n" +
            "41,81\n" +
            "42,67\n" +
            "43,472\n" +
            "44,173\n" +
            "45,209\n" +
            "46,135\n" +
            "47,218\n" +
            "48,69\n" +
            "49,137\n" +
            "52,324\n" +
            "54,210\n" +
            "55,330\n" +
            "56,316\n" +
            "57,436\n" +
            "58,212\n" +
            "59,193\n" +
            "61,233\n" +
            "62,211\n" +
            "63,158\n" +
            "64,439\n" +
            "65,419\n" +
            "66,455\n" +
            "70,153\n" +
            "71,198\n" +
            "73,283\n" +
            "74,76\n" +
            "75,250\n" +
            "77,418\n" +
            "78,191\n" +
            "79,144\n" +
            "80,352\n" +
            "82,195\n" +
            "85,192\n" +
            "86,329\n" +
            "87,340\n" +
            "88,306\n" +
            "89,181\n" +
            "90,299\n" +
            "91,383\n" +
            "92,358\n" +
            "93,276\n" +
            "95,119\n" +
            "96,176\n" +
            "97,129\n" +
            "98,235\n" +
            "99,487\n" +
            "101,336\n" +
            "102,332\n" +
            "104,183\n" +
            "105,281\n" +
            "107,432\n" +
            "109,273\n" +
            "110,416\n" +
            "111,304\n" +
            "112,465\n" +
            "113,385\n" +
            "114,167\n" +
            "115,497\n" +
            "116,399\n" +
            "117,404\n" +
            "118,384\n" +
            "121,450\n" +
            "122,247\n" +
            "124,486\n" +
            "125,402\n" +
            "127,344\n" +
            "130,175\n" +
            "131,310\n" +
            "133,149\n" +
            "134,147\n" +
            "136,289\n" +
            "138,453\n" +
            "139,184\n" +
            "140,351\n" +
            "141,256\n" +
            "142,422\n" +
            "143,440\n" +
            "145,481\n" +
            "146,201\n" +
            "148,293\n" +
            "150,231\n" +
            "151,170\n" +
            "152,223\n" +
            "154,314\n" +
            "155,395\n" +
            "156,249\n" +
            "157,414\n" +
            "159,341\n" +
            "160,446\n" +
            "161,410\n" +
            "162,286\n" +
            "163,166\n" +
            "164,307\n" +
            "165,242\n" +
            "168,282\n" +
            "172,234\n" +
            "174,224\n" +
            "177,320\n" +
            "178,258\n" +
            "179,433\n" +
            "182,461\n" +
            "186,257\n" +
            "187,312\n" +
            "188,339\n" +
            "189,388\n" +
            "190,373\n" +
            "194,325\n" +
            "196,322\n" +
            "197,427\n" +
            "200,483\n" +
            "202,357\n" +
            "204,268\n" +
            "205,206\n" +
            "207,285\n" +
            "208,244\n" +
            "213,425\n" +
            "214,294\n" +
            "215,354\n" +
            "216,420\n" +
            "217,382\n" +
            "219,297\n" +
            "220,378\n" +
            "222,400\n" +
            "226,323\n" +
            "229,337\n" +
            "230,499\n" +
            "237,437\n" +
            "238,408\n" +
            "239,489\n" +
            "241,405\n" +
            "243,389\n" +
            "245,392\n" +
            "246,361\n" +
            "248,364\n" +
            "252,424\n" +
            "253,454\n" +
            "254,374\n" +
            "255,301\n" +
            "259,292\n" +
            "260,409\n" +
            "261,347\n" +
            "262,280\n" +
            "263,451\n" +
            "265,381\n" +
            "266,379\n" +
            "267,355\n" +
            "271,456\n" +
            "272,369\n" +
            "274,298\n" +
            "275,431\n" +
            "277,412\n" +
            "278,473\n" +
            "284,490\n" +
            "287,494\n" +
            "288,413\n" +
            "290,343\n" +
            "291,396\n" +
            "295,348\n" +
            "300,315\n" +
            "302,464\n" +
            "303,345\n" +
            "305,468\n" +
            "308,480\n" +
            "309,448\n" +
            "311,331\n" +
            "313,463\n" +
            "317,495\n" +
            "318,367\n" +
            "321,438\n" +
            "327,366\n" +
            "334,426\n" +
            "338,466\n" +
            "342,346\n" +
            "350,445\n" +
            "353,471\n" +
            "356,447\n" +
            "363,476\n" +
            "365,415\n" +
            "370,442\n" +
            "372,458\n" +
            "375,434\n" +
            "376,462\n" +
            "377,423\n" +
            "380,406\n" +
            "386,469\n" +
            "387,459\n" +
            "390,498\n" +
            "391,479\n" +
            "394,496\n" +
            "397,485\n" +
            "401,457\n" +
            "403,474\n" +
            "407,470\n" +
            "411,452\n" +
            "417,443\n" +
            "421,430\n" +
            "435,475\n" +
            "467,493\n" +
            "488,500";

    public static String solve() {
        List<Pair> bPairs = parsePairs(BEDS_500);
        List<Pair> dPairs = parsePairs(DESKS_500);
        long ans = countValidPermutations(500, bPairs, dPairs);
        return Long.toString(ans);
    }

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