import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Euler486 {

    private static final long[] K_C = { 182L, 216L, 252L, 286L, 318L, 350L };
    private static final long[] K_PRIME_POWER_FACTORS = { 9L, 1997L, 4877L };
    private static final long K_MAIN_MOD = 87654321L;

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

    private static long lcmU64(long a, long b) {
        return (a / gcdU64(a, b)) * b;
    }

    private static List<Long> distinctPrimeFactors(long n) {
        List<Long> factors = new ArrayList<>();
        for (long p = 2; p * p <= n; ++p) {
            if (n % p == 0) {
                factors.add(p);
                while (n % p == 0) {
                    n /= p;
                }
            }
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    }

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

    private static long powMod(long base, long exp, long mod) {
        long res = 1 % mod;
        long cur = base % mod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                res = (res * cur) % mod;
            }
            cur = (cur * cur) % mod;
            exp >>= 1;
        }
        return res;
    }

    private static long multiplicativeOrder(long a, long mod) {
        if (gcdU64(a, mod) != 1)
            return 0;
        long order = eulerPhi(mod);
        List<Long> factors = distinctPrimeFactors(order);
        for (long p : factors) {
            while (order % p == 0 && powMod(a, order / p, mod) == 1) {
                order /= p;
            }
        }
        return order;
    }

    private static long[] computeF5Prefix(int maxN) {
        long[] f = new long[maxN + 1];
        List<long[]> states = new ArrayList<>();
        states.add(new long[] { 0, 1 }); // bits, count

        for (int n = 1; n <= maxN; ++n) {
            long[] nextCount = new long[32];
            for (long[] st : states) {
                long bits = st[0];
                long count = st[1];
                for (long add = 0; add <= 1; ++add) {
                    long combined = (bits << 1) | add;
                    boolean ok = true;

                    if (n >= 5) {
                        long v5 = combined & 31;
                        long b0 = (v5 >> 0) & 1, b1 = (v5 >> 1) & 1, b3 = (v5 >> 3) & 1, b4 = (v5 >> 4) & 1;
                        if (b0 == b4 && b1 == b3)
                            ok = false;
                    }

                    if (ok && n >= 6) {
                        long v6 = combined & 63;
                        long b0 = (v6 >> 0) & 1, b1 = (v6 >> 1) & 1, b2 = (v6 >> 2) & 1;
                        long b3 = (v6 >> 3) & 1, b4 = (v6 >> 4) & 1, b5 = (v6 >> 5) & 1;
                        if (b0 == b5 && b1 == b4 && b2 == b3)
                            ok = false;
                    }

                    if (!ok)
                        continue;

                    int nextBits = (n <= 5) ? (int) (combined & ((1 << n) - 1)) : (int) (combined & 31);
                    nextCount[nextBits] += count;
                }
            }

            states.clear();
            long totalA = 0;
            for (int mask = 0; mask < 32; ++mask) {
                if (nextCount[mask] != 0) {
                    states.add(new long[] { mask, nextCount[mask] });
                    totalA += nextCount[mask];
                }
            }

            long totalStrings = (n < 63) ? (1L << n) : 0L;
            f[n] = f[n - 1] + (totalStrings - totalA);
        }
        return f;
    }

    private static List<Long> computeResiduesForModU(long mod, long period, int u) {
        List<Long> residues = new ArrayList<>();
        long lhsMul = powMod(2, 10 + u, mod);
        long pow64 = 1 % mod;
        long rhs = K_C[u] % mod;

        for (long t = 0; t < period; ++t) {
            if ((lhsMul * pow64) % mod == rhs) {
                residues.add(t);
            }
            pow64 = (pow64 * 64) % mod;
            rhs = (rhs + 200) % mod;
        }
        return residues;
    }

    private static long modInverse(long a, long mod) {
        long t = 0, newT = 1;
        long r = mod, newR = a % mod;
        while (newR != 0) {
            long q = r / newR;
            long tempT = t - q * newT;
            t = newT;
            newT = tempT;

            long tempR = r - q * newR;
            r = newR;
            newR = tempR;
        }
        if (r != 1)
            return 0;
        long res = t % mod;
        if (res < 0)
            res += mod;
        return res;
    }

    static class CRTPrecompute {
        long m1, m2, g, m1DivG, m2DivG, lcm, invM1DivGModM2DivG;

        CRTPrecompute(long m1, long m2) {
            this.m1 = m1;
            this.m2 = m2;
            this.g = gcdU64(m1, m2);
            this.m1DivG = m1 / g;
            this.m2DivG = m2 / g;
            this.lcm = m1DivG * m2;
            this.invM1DivGModM2DivG = modInverse(this.m1DivG % this.m2DivG, this.m2DivG);
        }
    }

    private static long crtMergePair(long a, long b, CRTPrecompute crt) {
        long diff = b - a;
        long reduced = diff / crt.g;
        long k = reduced % crt.m2DivG;
        if (k < 0)
            k += crt.m2DivG;
        long t = (k * crt.invM1DivGModM2DivG) % crt.m2DivG;
        return (a + crt.m1 * t) % crt.lcm;
    }

    private static class MergeResult {
        List<Long> residues;
        long period;

        MergeResult(List<Long> residues, long period) {
            this.residues = residues;
            this.period = period;
        }
    }

    private static MergeResult combineResiduesForU(List<Long> mod1997, long p1997,
            List<Long> mod4877, long p4877,
            List<Long> mod9, long p9) {
        CRTPrecompute crt12 = new CRTPrecompute(p1997, p4877);
        CRTPrecompute crt129 = new CRTPrecompute(crt12.lcm, p9);

        long globalPeriod = crt129.lcm;

        List<Long> mod4877Even = new ArrayList<>();
        List<Long> mod4877Odd = new ArrayList<>();
        for (long v : mod4877) {
            if (v % 2 == 0)
                mod4877Even.add(v);
            else
                mod4877Odd.add(v);
        }

        List<Long> combined = new ArrayList<>();
        for (long a : mod1997) {
            List<Long> candidates = (a % 2 == 0) ? mod4877Even : mod4877Odd;
            for (long b : candidates) {
                long merged12 = crtMergePair(a, b, crt12);
                for (long c : mod9) {
                    long merged = crtMergePair(merged12, c, crt129);
                    combined.add(merged);
                }
            }
        }

        Collections.sort(combined);
        List<Long> unique = new ArrayList<>();
        for (Long v : combined) {
            if (unique.isEmpty() || !unique.get(unique.size() - 1).equals(v)) {
                unique.add(v);
            }
        }

        return new MergeResult(unique, globalPeriod);
    }

    private static long countFromResidues(List<Long> residues, long period, long tLimit) {
        if (residues.isEmpty())
            return 0;
        long full = tLimit / period;
        long rem = tLimit % period;
        int inTail = Collections.binarySearch(residues, rem);
        if (inTail < 0) {
            inTail = -(inTail + 1);
        } else {
            inTail++;
            while (inTail < residues.size() && residues.get(inTail) == rem) {
                inTail++;
            }
        }
        return full * residues.size() + inTail;
    }

    public static void main(String[] args) {
        long[] mods = K_PRIME_POWER_FACTORS;
        long[] periods = new long[3];
        List<List<Long>>[] residuesByU = new List[3];

        for (int i = 0; i < 3; i++) {
            long order = multiplicativeOrder(64 % mods[i], mods[i]);
            periods[i] = lcmU64(mods[i], order);
            residuesByU[i] = new ArrayList<>();
            for (int u = 0; u < 6; u++) {
                residuesByU[i].add(computeResiduesForModU(mods[i], periods[i], u));
            }
        }

        long[] smallF5 = computeF5Prefix(20);
        long[] smallF5Mod = new long[smallF5.length];
        for (int i = 0; i < smallF5.length; i++) {
            smallF5Mod[i] = smallF5[i] % K_MAIN_MOD;
        }

        List<List<Long>> globalResiduesByU = new ArrayList<>();
        long globalPeriod = 1;

        for (int u = 0; u < 6; u++) {
            MergeResult res = combineResiduesForU(
                    residuesByU[1].get(u), periods[1],
                    residuesByU[2].get(u), periods[2],
                    residuesByU[0].get(u), periods[0]);
            globalResiduesByU.add(res.residues);
            globalPeriod = res.period;
        }

        long limit = 1000000000000000000L;
        long answer = 0;
        long smallEnd = Math.min(limit, 8);
        for (int n = 5; n <= smallEnd; n++) {
            if (smallF5Mod[n] == 0)
                answer++;
        }

        if (limit >= 9) {
            for (int u = 0; u < 6; u++) {
                long n0 = 9 + u;
                if (n0 > limit)
                    continue;
                long tLimit = (limit - n0) / 6;
                answer += countFromResidues(globalResiduesByU.get(u), globalPeriod, tLimit);
            }
        }

        System.out.println(answer);
    }
}