import java.util.*;

public class Euler152 {
    static int[] sievePrimes(int limit) {
        boolean[] np = new boolean[limit + 1];
        np[0] = np[1] = true;
        for (int p = 2; p * p <= limit; p++)
            if (!np[p])
                for (int q = p * p; q <= limit; q += p)
                    np[q] = true;
        int c = 0;
        for (int i = 2; i <= limit; i++)
            if (!np[i])
                c++;
        int[] pr = new int[c];
        c = 0;
        for (int i = 2; i <= limit; i++)
            if (!np[i])
                pr[c++] = i;
        return pr;
    }

    static long modInverse(long a, long mod) {
        long t = 0, nt = 1, r = mod, nr = a % mod;
        while (nr != 0) {
            long q = r / nr;
            long tmp = nt;
            nt = t - q * nt;
            t = tmp;
            tmp = nr;
            nr = r - q * nr;
            r = tmp;
        }
        return ((t % mod) + mod) % mod;
    }

    public static void main(String[] args) {
        int limit = 80;
        int[] primes = sievePrimes(limit);
        // Build odd prime top groups
        List<int[]> groupNumbers = new ArrayList<>();
        List<int[][]> groupValid = new ArrayList<>();
        List<Integer> groupUsedUnion = new ArrayList<>();

        for (int p : primes) {
            if (p == 2)
                continue;
            int pp = p;
            while (pp <= limit / p)
                pp *= p;
            int npp = pp * p;
            List<Integer> nums = new ArrayList<>();
            for (int n = 2; n <= limit; n++) {
                if (n % pp != 0)
                    continue;
                if (npp <= limit && n % npp == 0)
                    continue;
                nums.add(n);
            }
            if (nums.isEmpty())
                continue;
            long mod = (long) p * p;
            long[] coeffs = new long[nums.size()];
            for (int i = 0; i < nums.size(); i++) {
                long m = nums.get(i) / pp;
                long sq = (m * m) % mod;
                coeffs[i] = modInverse(sq, mod);
            }
            List<Integer> validMasks = new ArrayList<>();
            int unionMask = 0;
            for (int mask = 0; mask < (1 << nums.size()); mask++) {
                long res = 0;
                for (int i = 0; i < nums.size(); i++)
                    if ((mask >> i & 1) == 1)
                        res = (res + coeffs[i]) % mod;
                if (res == 0) {
                    validMasks.add(mask);
                    unionMask |= mask;
                }
            }
            int[] na = nums.stream().mapToInt(Integer::intValue).toArray();
            int[][] va = { validMasks.stream().mapToInt(Integer::intValue).toArray() };
            groupNumbers.add(na);
            groupValid.add(va);
            groupUsedUnion.add(unionMask);
        }

        int[] numToGroup = new int[limit + 1], numToBit = new int[limit + 1];
        Arrays.fill(numToGroup, -1);
        Arrays.fill(numToBit, -1);
        for (int g = 0; g < groupNumbers.size(); g++) {
            int[] gn = groupNumbers.get(g);
            for (int i = 0; i < gn.length; i++) {
                numToGroup[gn[i]] = g;
                numToBit[gn[i]] = i;
            }
        }

        boolean[] possible = new boolean[limit + 1];
        List<Integer> freeNums = new ArrayList<>();
        for (int n = 2; n <= limit; n++) {
            int g = numToGroup[n];
            if (g == -1) {
                possible[n] = true;
                freeNums.add(n);
            } else if ((groupUsedUnion.get(g) >> numToBit[n] & 1) == 1)
                possible[n] = true;
        }

        long common = 1;
        for (int n = 2; n <= limit; n++)
            if (possible[n]) {
                common = common / gcd(common, n) * n;
            }
        long commonSq = common * common;
        long target = commonSq / 2;

        long[] weight = new long[limit + 1];
        for (int n = 2; n <= limit; n++)
            if (possible[n])
                weight[n] = commonSq / ((long) n * n);

        // Process groups
        Map<Long, Long> baseStates = new HashMap<>();
        baseStates.put(0L, 1L);
        for (int g = 0; g < groupNumbers.size(); g++) {
            int[] gn = groupNumbers.get(g);
            int[] vm = groupValid.get(g)[0];
            if (vm.length == 1 && vm[0] == 0)
                continue;
            Map<Long, Long> optCounts = new HashMap<>();
            for (int mask : vm) {
                long tot = 0;
                for (int i = 0; i < gn.length; i++)
                    if ((mask >> i & 1) == 1)
                        tot += weight[gn[i]];
                optCounts.merge(tot, 1L, Long::sum);
            }
            Map<Long, Long> next = new HashMap<>();
            for (var e1 : baseStates.entrySet())
                for (var e2 : optCounts.entrySet())
                    next.merge(e1.getKey() + e2.getKey(), e1.getValue() * e2.getValue(), Long::sum);
            baseStates = next;
        }

        // Meet in middle on free numbers
        long[] fw = freeNums.stream().mapToLong(n -> weight[n]).toArray();
        int mid = fw.length / 2;
        Map<Long, Long> leftCounts = subsetSums(fw, 0, mid);
        Map<Long, Long> rightCounts = subsetSums(fw, mid, fw.length);

        long count = 0;
        for (var be : baseStates.entrySet())
            for (var le : leftCounts.entrySet()) {
                long need = target - be.getKey() - le.getKey();
                Long rc = rightCounts.get(need);
                if (rc != null)
                    count += be.getValue() * le.getValue() * rc;
            }
        System.out.println(count);
    }

    static Map<Long, Long> subsetSums(long[] w, int from, int to) {
        Map<Long, Long> counts = new HashMap<>();
        for (int mask = 0; mask < (1 << (to - from)); mask++) {
            long s = 0;
            for (int i = 0; i < to - from; i++)
                if ((mask >> i & 1) == 1)
                    s += w[from + i];
            counts.merge(s, 1L, Long::sum);
        }
        return counts;
    }

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