import java.util.*;

public class Euler833 {

    static final long kMod = 136101521L;

    static class PairInfo {
        int iIdx;
        int jIdx;
        long kMax;
        long[] poly;
        long sumAll = 0;
        long sumNf = 0;
    }

    static boolean mulLeq(long a, long b, long limit) {
        if (a == 0 || b == 0)
            return true;
        if (a > limit / b)
            return false;
        return true;
    }

    static boolean evalPairLeq(long k, int iIdx, int jIdx, double limit) {
        // Since limit could be 10^35, we can't do exact long.
        // We'll use BigInteger maybe? Or simply approximate with double for upper
        // bounds.
        // wait, 10^35 fits in standard double ~1.7e308. Wait, exact arithmetic is
        // better.
        return true;
    }

    // Implementing exact 128 bit behavior with BigInteger
    static java.math.BigInteger toBI(long v) {
        return java.math.BigInteger.valueOf(v);
    }

    static boolean mulLeq(java.math.BigInteger a, java.math.BigInteger b, java.math.BigInteger limit,
            java.math.BigInteger[] out) {
        if (a.equals(java.math.BigInteger.ZERO) || b.equals(java.math.BigInteger.ZERO)) {
            out[0] = java.math.BigInteger.ZERO;
            return true;
        }
        java.math.BigInteger p = a.multiply(b);
        if (p.compareTo(limit) > 0)
            return false;
        out[0] = p;
        return true;
    }

    static boolean evalPairLeq(long k, int iIdx, int jIdx, java.math.BigInteger limit) {
        java.math.BigInteger kk = toBI(k);
        java.math.BigInteger x = kk.multiply(toBI(2)).add(java.math.BigInteger.ONE);
        int maxIdx = Math.max(iIdx, jIdx);
        java.math.BigInteger[] U = new java.math.BigInteger[maxIdx + 1];
        U[0] = java.math.BigInteger.ONE;
        if (maxIdx >= 1)
            U[1] = x.multiply(toBI(2));

        java.math.BigInteger twoX = x.multiply(toBI(2));
        for (int m = 1; m < maxIdx; ++m) {
            java.math.BigInteger thresh = limit.add(U[m - 1]).divide(twoX);
            if (U[m].compareTo(thresh) > 0) {
                U[m + 1] = limit.add(java.math.BigInteger.ONE);
            } else {
                java.math.BigInteger next = twoX.multiply(U[m]).subtract(U[m - 1]);
                U[m + 1] = next.compareTo(limit) > 0 ? limit.add(java.math.BigInteger.ONE) : next;
            }
        }

        java.math.BigInteger t = kk.multiply(kk.add(java.math.BigInteger.ONE)).divide(toBI(2));
        java.math.BigInteger[] tmp = new java.math.BigInteger[1];
        if (!mulLeq(t, U[iIdx], limit, tmp))
            return false;
        if (!mulLeq(tmp[0], U[jIdx], limit, tmp))
            return false;
        return true;
    }

    static long maxKForPair(java.math.BigInteger n, int iIdx, int jIdx) {
        long lo = 0;
        long hi = 1;
        while (evalPairLeq(hi, iIdx, jIdx, n)) {
            if (hi > (Long.MAX_VALUE / 2))
                break;
            hi *= 2;
        }
        while (lo + 1 < hi) {
            long mid = lo + (hi - lo) / 2;
            if (evalPairLeq(mid, iIdx, jIdx, n)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    static ArrayList<Long> generateNonFundamentals(long kMax) {
        ArrayList<Long> nf = new ArrayList<>();
        if (kMax < 4)
            return nf;
        long k1Max = (long) Math.sqrt((double) kMax / 4.0) + 2;
        for (long k1 = 1; k1 <= k1Max; ++k1) {
            java.math.BigInteger x1 = toBI(2 * k1 + 1);
            java.math.BigInteger xPrev = java.math.BigInteger.ONE;
            java.math.BigInteger xCur = x1;
            while (true) {
                java.math.BigInteger xNext = toBI(2).multiply(x1).multiply(xCur).subtract(xPrev);
                java.math.BigInteger kNextBI = xNext.subtract(java.math.BigInteger.ONE).divide(toBI(2));
                if (kNextBI.compareTo(toBI(kMax)) > 0)
                    break;
                nf.add(kNextBI.longValue());
                xPrev = xCur;
                xCur = xNext;
            }
        }
        Collections.sort(nf);
        ArrayList<Long> distinctNf = new ArrayList<>();
        for (long v : nf) {
            if (distinctNf.isEmpty() || distinctNf.get(distinctNf.size() - 1) != v) {
                distinctNf.add(v);
            }
        }
        return distinctNf;
    }

    static long modPow(long base, long exp) {
        long res = 1 % kMod;
        base %= kMod;
        while (exp > 0) {
            if ((exp & 1) == 1)
                res = (res * base) % kMod;
            base = (base * base) % kMod;
            exp >>= 1;
        }
        return res;
    }

    static long modInv(long a) {
        return modPow(a, kMod - 2);
    }

    static long[] polyScale(long[] a, long s) {
        long[] c = new long[a.length];
        for (int i = 0; i < a.length; ++i) {
            c[i] = (a[i] * s) % kMod;
        }
        return c;
    }

    static long[] polySub(long[] a, long[] b) {
        int n = Math.max(a.length, b.length);
        long[] c = new long[n];
        for (int i = 0; i < n; ++i) {
            long va = i < a.length ? a[i] : 0;
            long vb = i < b.length ? b[i] : 0;
            c[i] = (va - vb) % kMod;
            if (c[i] < 0)
                c[i] += kMod;
        }
        return c;
    }

    static long[] polyMul(long[] a, long[] b) {
        long[] c = new long[a.length + b.length - 1];
        for (int i = 0; i < a.length; ++i) {
            for (int j = 0; j < b.length; ++j) {
                c[i + j] = (c[i + j] + a[i] * b[j]) % kMod;
            }
        }
        return c;
    }

    static long[][] buildUPolys(int maxIdx) {
        long[] t = { 1, 2 };
        long[][] U = new long[maxIdx + 1][];
        U[0] = new long[] { 1 };
        if (maxIdx >= 1)
            U[1] = polyScale(t, 2);

        for (int m = 1; m < maxIdx; ++m) {
            long[] temp = polyMul(t, U[m]);
            temp = polyScale(temp, 2);
            U[m + 1] = polySub(temp, U[m - 1]);
        }
        return U;
    }

    static class SumPowers {
        long[][] y;
        long[] fact;
        long[] invfact;
    }

    static SumPowers precomputeSumPows(int maxP) {
        SumPowers sp = new SumPowers();
        sp.y = new long[maxP + 1][maxP + 2];
        for (int p = 0; p <= maxP; ++p) {
            int m = p + 1;
            long s = 0;
            for (int i = 1; i <= m; ++i) {
                s = (s + modPow(i, p)) % kMod;
                sp.y[p][i] = s;
            }
        }
        sp.fact = new long[maxP + 2];
        sp.invfact = new long[maxP + 2];
        sp.fact[0] = 1;
        sp.invfact[0] = 1;
        for (int i = 1; i < sp.fact.length; ++i) {
            sp.fact[i] = (sp.fact[i - 1] * i) % kMod;
        }
        sp.invfact[sp.invfact.length - 1] = modInv(sp.fact[sp.fact.length - 1]);
        for (int i = sp.fact.length - 1; i >= 1; --i) {
            sp.invfact[i - 1] = (sp.invfact[i] * i) % kMod;
        }
        return sp;
    }

    static long sumPows(int p, long n, SumPowers sp) {
        if (n <= p + 1) {
            return sp.y[p][(int) n];
        }
        int m = p + 1;
        long[] pre = new long[m + 2];
        long[] suf = new long[m + 2];
        pre[0] = 1;
        suf[m + 1] = 1;
        long nmod = n % kMod;

        for (int i = 0; i <= m; ++i) {
            long term = (nmod - i) % kMod;
            if (term < 0)
                term += kMod;
            pre[i + 1] = (pre[i] * term) % kMod;
        }
        for (int i = m; i >= 0; --i) {
            long term = (nmod - i) % kMod;
            if (term < 0)
                term += kMod;
            suf[i] = (suf[i + 1] * term) % kMod;
        }

        long res = 0;
        for (int i = 0; i <= m; ++i) {
            long num = (pre[i] * suf[i + 1]) % kMod;
            long denomInv = (sp.invfact[i] * sp.invfact[m - i]) % kMod;
            long term = (sp.y[p][i] * num) % kMod;
            term = (term * denomInv) % kMod;
            if ((m - i) % 2 != 0) {
                if (term != 0)
                    term = kMod - term;
            }
            res = (res + term) % kMod;
        }
        return res;
    }

    static long sumPoly(long[] coeffs, long n, SumPowers sp) {
        long res = 0;
        for (int p = 0; p < coeffs.length; ++p) {
            if (coeffs[p] == 0)
                continue;
            long spow = sumPows(p, n, sp);
            res = (res + coeffs[p] * spow) % kMod;
        }
        return res;
    }

    public static String solve() {
        java.math.BigInteger n = java.math.BigInteger.TEN.pow(35);

        ArrayList<java.math.BigInteger> U3 = new ArrayList<>();
        U3.add(java.math.BigInteger.ONE);
        U3.add(toBI(6));
        while (true) {
            java.math.BigInteger next = toBI(6).multiply(U3.get(U3.size() - 1)).subtract(U3.get(U3.size() - 2));
            U3.add(next);
            if (next.compareTo(n) > 0)
                break;
        }

        int maxIdx = U3.size() - 1;
        ArrayList<PairInfo> pairs = new ArrayList<>();

        for (int i = 0; i <= maxIdx; ++i) {
            for (int j = i + 1; j <= maxIdx; ++j) {
                java.math.BigInteger[] tmp = new java.math.BigInteger[1];
                if (!mulLeq(U3.get(i), U3.get(j), n, tmp))
                    continue;
                PairInfo info = new PairInfo();
                info.iIdx = i;
                info.jIdx = j;
                pairs.add(info);
            }
        }

        long maxK = 0;
        for (PairInfo p : pairs) {
            p.kMax = maxKForPair(n, p.iIdx, p.jIdx);
            maxK = Math.max(maxK, p.kMax);
        }

        ArrayList<Long> nf = generateNonFundamentals(maxK);

        long inv2 = modInv(2);
        long[][] UPolys = buildUPolys(maxIdx);
        long[] tPoly = { 0, inv2, inv2 };
        int degMax = 0;

        for (PairInfo p : pairs) {
            long[] r = polyMul(UPolys[p.iIdx], UPolys[p.jIdx]);
            p.poly = polyMul(r, tPoly);
            degMax = Math.max(degMax, p.poly.length - 1);
        }

        SumPowers sp = precomputeSumPows(degMax);
        for (PairInfo p : pairs) {
            p.sumAll = sumPoly(p.poly, p.kMax, sp);
        }

        for (PairInfo p : pairs) {
            p.sumNf = 0;
            for (long k : nf) {
                if (k > p.kMax)
                    continue;
                long kModV = k % kMod;
                long xMod = (2 * kModV + 1) % kMod;
                long[] U = new long[maxIdx + 1];
                U[0] = 1;
                if (maxIdx >= 1)
                    U[1] = (2 * xMod) % kMod;
                for (int m = 1; m < maxIdx; ++m) {
                    U[m + 1] = (2 * xMod * U[m] - U[m - 1]) % kMod;
                    if (U[m + 1] < 0)
                        U[m + 1] += kMod;
                }
                long t = (kModV * ((kModV + 1) % kMod)) % kMod;
                t = (t * inv2) % kMod;

                long val = (t * U[p.iIdx]) % kMod;
                val = (val * U[p.jIdx]) % kMod;

                p.sumNf = (p.sumNf + val) % kMod;
            }
        }

        long ans = 0;
        for (PairInfo p : pairs) {
            long term = (p.sumAll - p.sumNf) % kMod;
            if (term < 0)
                term += kMod;
            ans = (ans + term) % kMod;
        }

        return Long.toString(ans);
    }

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