import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Euler1006 {
    private static final long MOD = 101_001_001L;
    private static final long BASE = 10L;
    private static final long TARGET = 1_000_000_000_000_000_000L;

    private static long normalize(long value) {
        value %= MOD;
        if (value < 0) {
            value += MOD;
        }
        return value;
    }

    private static long modPow(long base, long exponent) {
        long result = 1;
        base = normalize(base);
        while (exponent > 0) {
            if ((exponent & 1L) != 0) {
                result = result * base % MOD;
            }
            base = base * base % MOD;
            exponent >>= 1;
        }
        return result;
    }

    private static final class Bezout {
        long gcd;
        long x;
        long y;

        Bezout(long gcd, long x, long y) {
            this.gcd = gcd;
            this.x = x;
            this.y = y;
        }
    }

    private static Bezout extendedGcd(long a, long b) {
        if (b == 0) {
            return new Bezout(a, 1, 0);
        }
        Bezout next = extendedGcd(b, a % b);
        return new Bezout(next.gcd, next.y, next.x - (a / b) * next.y);
    }

    private static long modInverse(long value) {
        Bezout result = extendedGcd(normalize(value), MOD);
        if (result.gcd != 1) {
            throw new ArithmeticException("a required modular inverse does not exist");
        }
        return normalize(result.x);
    }

    private static final class Node {
        long length;
        int left;
        int right;
        int bit;

        Node(long length, int left, int right, int bit) {
            this.length = length;
            this.left = left;
            this.right = right;
            this.bit = bit;
        }
    }

    private static final class Summary {
        long forward;
        long reverse;
        long pairs;
        long ones;

        Summary(long forward, long reverse, long pairs, long ones) {
            this.forward = forward;
            this.reverse = reverse;
            this.pairs = pairs;
            this.ones = ones;
        }
    }

    private record PairKey(int left, int right) {}

    private record PrefixKey(int standardIndex, long length) {}

    private record QueryKey(int x, int y, long low, long high, int baseId) {}

    private static final class FibonacciSubwords {
        private final List<Node> nodes = new ArrayList<>();
        private final List<Summary[]> summaryCache = new ArrayList<>();
        private final Map<PairKey, Integer> concatenationCache = new HashMap<>();
        private final Map<PrefixKey, Integer> prefixCache = new HashMap<>();
        private final List<Long> fibonacci = new ArrayList<>();
        private final List<Integer> standard = new ArrayList<>();
        private final long[] bases = new long[2];
        private final List<Map<Long, Long>> powerCache =
                List.of(new HashMap<>(), new HashMap<>());
        private final Map<QueryKey, Long> sumQueryCache = new HashMap<>();
        private final Map<QueryKey, Long> differenceQueryCache = new HashMap<>();
        private final int zero;
        private final int one;

        FibonacciSubwords() {
            bases[0] = BASE;
            bases[1] = modInverse(BASE);

            zero = addBit(0);
            one = addBit(1);
            fibonacci.add(1L);
            fibonacci.add(2L);
            standard.add(zero);
            standard.add(concatenate(zero, one));

            while (fibonacci.get(fibonacci.size() - 1) <= TARGET) {
                fibonacci.add(
                        fibonacci.get(fibonacci.size() - 1)
                                + fibonacci.get(fibonacci.size() - 2));
                standard.add(
                        concatenate(
                                standard.get(standard.size() - 1),
                                standard.get(standard.size() - 2)));
            }
        }

        private int addBit(int bit) {
            int id = nodes.size();
            nodes.add(new Node(1, -1, -1, bit));
            summaryCache.add(new Summary[2]);
            return id;
        }

        private int concatenate(int left, int right) {
            if (left < 0) {
                return right;
            }
            if (right < 0) {
                return left;
            }

            PairKey key = new PairKey(left, right);
            Integer cached = concatenationCache.get(key);
            if (cached != null) {
                return cached;
            }

            int id = nodes.size();
            nodes.add(
                    new Node(
                            nodes.get(left).length + nodes.get(right).length,
                            left,
                            right,
                            -1));
            summaryCache.add(new Summary[2]);
            concatenationCache.put(key, id);
            return id;
        }

        private int prefix(int standardIndex, long length) {
            require(
                    length > 0 && length <= fibonacci.get(standardIndex),
                    "invalid Fibonacci-word prefix");
            if (length == fibonacci.get(standardIndex)) {
                return standard.get(standardIndex);
            }

            PrefixKey key = new PrefixKey(standardIndex, length);
            Integer cached = prefixCache.get(key);
            if (cached != null) {
                return cached;
            }

            require(standardIndex > 0, "prefix recursion reached S_0");
            int result;
            if (length <= fibonacci.get(standardIndex - 1)) {
                result = prefix(standardIndex - 1, length);
            } else {
                result =
                        concatenate(
                                standard.get(standardIndex - 1),
                                prefix(
                                        standardIndex - 2,
                                        length - fibonacci.get(standardIndex - 1)));
            }

            prefixCache.put(key, result);
            return result;
        }

        private long power(int baseId, long exponent) {
            Map<Long, Long> cache = powerCache.get(baseId);
            Long cached = cache.get(exponent);
            if (cached != null) {
                return cached;
            }
            long result = modPow(bases[baseId], exponent);
            cache.put(exponent, result);
            return result;
        }

        private long signedPower(int baseId, long exponent) {
            if (exponent >= 0) {
                return power(baseId, exponent);
            }
            return power(1 - baseId, -exponent);
        }

        private Summary summarize(int nodeId, int baseId) {
            Summary cached = summaryCache.get(nodeId)[baseId];
            if (cached != null) {
                return cached;
            }

            Node node = nodes.get(nodeId);
            Summary result;
            if (node.bit >= 0) {
                result = new Summary(node.bit, node.bit, 0, node.bit);
                summaryCache.get(nodeId)[baseId] = result;
                return result;
            }

            Summary left = summarize(node.left, baseId);
            Summary right = summarize(node.right, baseId);
            long leftLength = nodes.get(node.left).length;
            long rightLength = nodes.get(node.right).length;
            long base = bases[baseId];

            result =
                    new Summary(
                            normalize(left.forward + power(baseId, leftLength) * right.forward),
                            normalize(power(baseId, rightLength) * left.reverse + right.reverse),
                            normalize(
                                    left.pairs
                                            + right.pairs
                                            + base * left.reverse % MOD * right.forward),
                            normalize(left.ones + right.ones));
            summaryCache.get(nodeId)[baseId] = result;
            return result;
        }

        private long sumQuery(int x, int y, long low, long high, int baseId) {
            if (x > y) {
                int temporary = x;
                x = y;
                y = temporary;
            }

            QueryKey key = new QueryKey(x, y, low, high, baseId);
            Long cached = sumQueryCache.get(key);
            if (cached != null) {
                return cached;
            }

            Node nodeX = nodes.get(x);
            Node nodeY = nodes.get(y);
            long maximum = nodeX.length + nodeY.length - 2;
            long result;

            if (high < 0 || low > maximum) {
                result = 0;
            } else if (low <= 0 && maximum <= high) {
                result = summarize(x, baseId).forward * summarize(y, baseId).forward % MOD;
            } else if (nodeX.bit >= 0 && nodeY.bit >= 0) {
                result = low <= 0 && 0 <= high ? (long) nodeX.bit * nodeY.bit : 0;
            } else if (nodeX.length >= nodeY.length && nodeX.bit < 0) {
                long offset = nodes.get(nodeX.left).length;
                result =
                        normalize(
                                sumQuery(nodeX.left, y, low, high, baseId)
                                        + power(baseId, offset)
                                                * sumQuery(
                                                        nodeX.right,
                                                        y,
                                                        low - offset,
                                                        high - offset,
                                                        baseId));
            } else {
                long offset = nodes.get(nodeY.left).length;
                result =
                        normalize(
                                sumQuery(x, nodeY.left, low, high, baseId)
                                        + power(baseId, offset)
                                                * sumQuery(
                                                        x,
                                                        nodeY.right,
                                                        low - offset,
                                                        high - offset,
                                                        baseId));
            }

            sumQueryCache.put(key, result);
            return result;
        }

        private long differenceQuery(int x, int y, long low, long high, int baseId) {
            QueryKey key = new QueryKey(x, y, low, high, baseId);
            Long cached = differenceQueryCache.get(key);
            if (cached != null) {
                return cached;
            }

            Node nodeX = nodes.get(x);
            Node nodeY = nodes.get(y);
            long minimum = -(nodeX.length - 1);
            long maximum = nodeY.length - 1;
            long result;

            if (high < minimum || low > maximum) {
                result = 0;
            } else if (low <= minimum && maximum <= high) {
                result =
                        summarize(x, 1 - baseId).forward
                                * summarize(y, baseId).forward
                                % MOD;
            } else if (nodeX.bit >= 0 && nodeY.bit >= 0) {
                result = low <= 0 && 0 <= high ? (long) nodeX.bit * nodeY.bit : 0;
            } else if (nodeX.length >= nodeY.length && nodeX.bit < 0) {
                long offset = nodes.get(nodeX.left).length;
                result =
                        normalize(
                                differenceQuery(nodeX.left, y, low, high, baseId)
                                        + signedPower(baseId, -offset)
                                                * differenceQuery(
                                                        nodeX.right,
                                                        y,
                                                        low + offset,
                                                        high + offset,
                                                        baseId));
            } else {
                long offset = nodes.get(nodeY.left).length;
                result =
                        normalize(
                                differenceQuery(x, nodeY.left, low, high, baseId)
                                        + power(baseId, offset)
                                                * differenceQuery(
                                                        x,
                                                        nodeY.right,
                                                        low - offset,
                                                        high - offset,
                                                        baseId));
            }

            differenceQueryCache.put(key, result);
            return result;
        }

        private long duplicatedWindowSum(int standardIndex, long k, long count) {
            if (count == 0) {
                return 0;
            }

            int initialWord = prefix(standardIndex, k);
            long initialValue = summarize(initialWord, 0).reverse;
            if (count == 1) {
                return initialValue * initialValue % MOD;
            }

            long transitionCount = count - 1;
            int outgoing = prefix(standardIndex, transitionCount);
            Summary outgoingSummary = summarize(outgoing, 0);
            long windowPower = power(0, k);
            long forwardDelta =
                    normalize(outgoingSummary.reverse - windowPower * outgoingSummary.forward);
            long reverseDelta =
                    normalize(outgoingSummary.forward - windowPower * outgoingSummary.reverse);

            long lowInverse = sumQuery(outgoing, outgoing, 0, transitionCount - 2, 1);
            long highBase =
                    sumQuery(
                            outgoing,
                            outgoing,
                            transitionCount,
                            2 * transitionCount - 2,
                            0);
            long diagonalBase =
                    sumQuery(
                            outgoing,
                            outgoing,
                            transitionCount - 1,
                            transitionCount - 1,
                            0);

            long diagonal = diagonalBase * power(1, transitionCount - 1) % MOD;
            long lowerCross = power(0, transitionCount - 1) * lowInverse % MOD;
            long upperCross = power(1, transitionCount - 1) * highBase % MOD;
            long deltaPairs =
                    normalize(
                            normalize(1 + windowPower * windowPower) * outgoingSummary.pairs
                                    - windowPower * normalize(lowerCross + upperCross));
            long deltaSquares =
                    normalize(
                            normalize(1 + windowPower * windowPower) * outgoingSummary.ones
                                    - 2 * windowPower % MOD * diagonal);

            long lastValue =
                    normalize(power(0, transitionCount) * initialValue + reverseDelta);
            long valueDeltaSum =
                    normalize(initialValue * forwardDelta + bases[1] * deltaPairs);
            long numerator =
                    normalize(
                            initialValue * initialValue
                                    - BASE * BASE % MOD * lastValue % MOD * lastValue
                                    + 2 * BASE % MOD * valueDeltaSum
                                    + deltaSquares);

            return numerator * modInverse(1 - BASE * BASE) % MOD;
        }

        long solve(long k) {
            int index = upperBound(fibonacci, k);
            require(index < fibonacci.size(), "target exceeds the prepared Fibonacci words");
            long cycleLength = fibonacci.get(index);
            long duplicateCount = cycleLength - 1 - k;
            long gapLength = duplicateCount + 1;
            int word = standard.get(index);

            Summary wordBase = summarize(word, 0);
            Summary wordInverse = summarize(word, 1);
            long cyclePower = power(0, cycleLength);
            long inverseCyclePower = power(1, cycleLength);

            long allCorrelationsBase =
                    normalize(wordBase.pairs + cyclePower * wordInverse.pairs);
            long allCorrelationsInverse =
                    normalize(wordInverse.pairs + inverseCyclePower * wordBase.pairs);

            long prefixCorrelationsBase =
                    normalize(
                            differenceQuery(word, word, 1, gapLength, 0)
                                    + cyclePower
                                            * differenceQuery(
                                                    word,
                                                    word,
                                                    cycleLength - gapLength,
                                                    cycleLength - 1,
                                                    1));
            long prefixCorrelationsInverse =
                    normalize(
                            differenceQuery(word, word, 1, gapLength, 1)
                                    + inverseCyclePower
                                            * differenceQuery(
                                                    word,
                                                    word,
                                                    cycleLength - gapLength,
                                                    cycleLength - 1,
                                                    0));

            long usedCorrelationsBase =
                    normalize(allCorrelationsBase - cyclePower * prefixCorrelationsInverse);
            long usedCorrelationsInverse =
                    normalize(
                            allCorrelationsInverse
                                    - inverseCyclePower * prefixCorrelationsBase);

            long inverseGeometricDenominator = modInverse(BASE * BASE - 1);
            long geometricSquares =
                    normalize(power(0, 2 * k) - 1) * inverseGeometricDenominator % MOD;
            long fullCycle =
                    normalize(
                            wordBase.ones * geometricSquares
                                    + 2
                                            * inverseGeometricDenominator
                                            % MOD
                                            * normalize(
                                                    power(0, 2 * k)
                                                                    * usedCorrelationsInverse
                                                            - usedCorrelationsBase));

            return normalize(
                    fullCycle - duplicatedWindowSum(index, k, duplicateCount));
        }
    }

    private static int upperBound(List<Long> values, long target) {
        int low = 0;
        int high = values.size();
        while (low < high) {
            int middle = (low + high) >>> 1;
            if (values.get(middle) <= target) {
                low = middle + 1;
            } else {
                high = middle;
            }
        }
        return low;
    }

    private static long bruteForce(int k) {
        String older = "0";
        String newer = "01";
        while (newer.length() < 10 * k + 20) {
            String next = newer + older;
            older = newer;
            newer = next;
        }

        Set<String> factors = new HashSet<>();
        for (int start = 0; start + k <= newer.length(); ++start) {
            factors.add(newer.substring(start, start + k));
        }
        require(factors.size() == k + 1, "factor complexity for k=" + k);

        long result = 0;
        for (String factor : factors) {
            long value = 0;
            for (int i = 0; i < factor.length(); ++i) {
                value = (BASE * value + factor.charAt(i) - '0') % MOD;
            }
            result = (result + value * value) % MOD;
        }
        return result;
    }

    private static void require(boolean condition, String message) {
        if (!condition) {
            throw new AssertionError("checkpoint failed: " + message);
        }
    }

    private static void runCheckpoints() {
        FibonacciSubwords solver = new FibonacciSubwords();
        require(bruteForce(3) == 20_302, "Psi(3)");
        for (int k = 1; k <= 50; ++k) {
            require(
                    solver.solve(k) == bruteForce(k),
                    "brute-force comparison for k=" + k);
        }
        require(solver.solve(10) == 10_699_667, "supplied Psi(10)");
        System.err.println("Validation checkpoints passed.");
    }

    public static void main(String[] args) {
        runCheckpoints();
        FibonacciSubwords solver = new FibonacciSubwords();
        System.out.println(solver.solve(TARGET));
    }
}