import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class Euler768 {

    static ArrayList<Long> trimPoly(ArrayList<Long> poly) {
        while (poly.size() > 1 && poly.get(poly.size() - 1) == 0L) {
            poly.remove(poly.size() - 1);
        }
        return poly;
    }

    static ArrayList<Long> dividePoly(ArrayList<Long> aList, ArrayList<Long> bList) {
        long[] a = new long[aList.size()];
        for (int i = 0; i < a.length; i++)
            a[i] = aList.get(i);
        long[] b = new long[bList.size()];
        for (int i = 0; i < b.length; i++)
            b[i] = bList.get(i);

        int da = a.length - 1;
        int db = b.length - 1;
        long[] q = new long[Math.max(0, da - db + 1)];

        for (int i = da; i >= db; --i) {
            long coef = a[i];
            if (coef == 0)
                continue;
            q[i - db] = coef;
            for (int j = 0; j <= db; ++j) {
                a[i - db + j] -= coef * b[j];
            }
        }

        ArrayList<Long> res = new ArrayList<>();
        for (long val : q)
            res.add(val);
        return trimPoly(res);
    }

    static ArrayList<Long> cyclotomic(int n) {
        ArrayList<ArrayList<Long>> phi = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++)
            phi.add(new ArrayList<>());

        phi.get(1).add(-1L);
        phi.get(1).add(1L);

        for (int k = 2; k <= n; ++k) {
            ArrayList<Long> poly = new ArrayList<>();
            for (int i = 0; i <= k; i++)
                poly.add(0L);
            poly.set(0, -1L);
            poly.set(k, 1L);

            for (int d = 1; d < k; ++d) {
                if (k % d == 0) {
                    poly = dividePoly(poly, phi.get(d));
                }
            }
            phi.set(k, trimPoly(poly));
        }
        return phi.get(n);
    }

    static int[] multiplyByX(int[] v, int[] rel) {
        int d = v.length;
        int[] res = new int[d];
        for (int i = 0; i + 1 < d; ++i) {
            res[i + 1] += v[i];
        }
        int h = v[d - 1];
        if (h != 0) {
            for (int i = 0; i < d; ++i) {
                res[i] -= h * rel[i];
            }
        }
        return res;
    }

    static long[] countZeroSums(int S, int m) {
        ArrayList<Long> phi = cyclotomic(S);
        int d = phi.size() - 1;
        int[] rel = new int[d];
        for (int i = 0; i < d; ++i)
            rel[i] = phi.get(i).intValue();

        int[][] powers = new int[S][d];
        powers[0][0] = 1;
        for (int i = 1; i < S; ++i) {
            powers[i] = multiplyByX(powers[i - 1], rel);
        }

        int mid = S / 2;
        int rightN = S - mid;

        HashMap<Long, int[]> leftSums = new HashMap<>(1 << mid);

        for (int mask = 0; mask < (1 << mid); ++mask) {
            int cnt = Integer.bitCount(mask);
            if (cnt > m)
                continue;

            long key = 0;
            int[] sumArr = new int[d];
            for (int k = 0; k < mid; ++k) {
                if (((mask >> k) & 1) != 0) {
                    for (int i = 0; i < d; ++i)
                        sumArr[i] += powers[k][i];
                }
            }

            for (int i = 0; i < d; ++i) {
                long val = sumArr[i] + 30; // offset by 30 to keep it positive
                key = (key << 8) | val;
            }

            int[] counts = leftSums.get(key);
            if (counts == null) {
                counts = new int[m + 1];
                leftSums.put(key, counts);
            }
            counts[cnt]++;
        }

        long[] total = new long[m + 1];

        for (int mask = 0; mask < (1 << rightN); ++mask) {
            int cnt = Integer.bitCount(mask);
            if (cnt > m)
                continue;

            long key = 0;
            int[] sumArr = new int[d];
            for (int k = 0; k < rightN; ++k) {
                if (((mask >> k) & 1) != 0) {
                    for (int i = 0; i < d; ++i)
                        sumArr[i] -= powers[mid + k][i];
                }
            }

            for (int i = 0; i < d; ++i) {
                long val = sumArr[i] + 30;
                key = (key << 8) | val;
            }

            int[] counts = leftSums.get(key);
            if (counts != null) {
                for (int lc = 0; lc + cnt <= m; ++lc) {
                    int ways = counts[lc];
                    if (ways > 0) {
                        total[lc + cnt] += ways;
                    }
                }
            }
        }
        return total;
    }

    static int radical(int n) {
        int res = 1;
        int x = n;
        for (int p = 2; p * p <= x; ++p) {
            if (x % p == 0) {
                res *= p;
                while (x % p == 0)
                    x /= p;
            }
        }
        if (x > 1)
            res *= x;
        return res;
    }

    static BigInteger[] multiplyPoly(BigInteger[] a, BigInteger[] b, int maxDeg) {
        int newDeg = Math.min(maxDeg, a.length + b.length - 2);
        BigInteger[] res = new BigInteger[newDeg + 1];
        Arrays.fill(res, BigInteger.ZERO);

        for (int i = 0; i < a.length; ++i) {
            if (a[i].equals(BigInteger.ZERO))
                continue;
            for (int j = 0; j < b.length; ++j) {
                if (b[j].equals(BigInteger.ZERO))
                    continue;
                if (i + j <= maxDeg) {
                    res[i + j] = res[i + j].add(a[i].multiply(b[j]));
                }
            }
        }
        return res;
    }

    static BigInteger solveChandelier(int n, int m) {
        if (m < 0 || m > n)
            return BigInteger.ZERO;
        if (m == 0)
            return BigInteger.ONE;

        int S = radical(n);
        int G = n / S;

        long[] counts = countZeroSums(S, m);
        BigInteger[] P = new BigInteger[m + 1];
        for (int k = 0; k <= m; ++k)
            P[k] = BigInteger.valueOf(counts[k]);

        BigInteger[] Final = new BigInteger[] { BigInteger.ONE };
        for (int i = 0; i < G; ++i) {
            Final = multiplyPoly(Final, P, m);
        }

        return (m < Final.length) ? Final[m] : BigInteger.ZERO;
    }

    public static String solve() {
        BigInteger ans = solveChandelier(360, 20);
        return ans.toString();
    }

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