import java.util.*;

public class Euler361 {
    static final long MOD = 1000000000L;

    static final String[][] kBaseFactors = {
            {},
            { "0", "1" },
            { "00", "01", "10", "11" },
            { "001", "010", "011", "100", "101", "110" }
    };

    static Map<Long, Long> pCache = new HashMap<>();
    static Map<Long, Long> sCache = new HashMap<>();

    static long pCount(long n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 2;
        if (n == 2)
            return 4;
        if (n == 3)
            return 6;
        if (pCache.containsKey(n))
            return pCache.get(n);
        long res = 0;
        if (n % 2 == 0) {
            long m = n / 2;
            res = pCount(m) + pCount(m + 1);
        } else {
            long m = n / 2;
            res = 2L * pCount(m + 1);
        }
        pCache.put(n, res);
        return res;
    }

    static long sCount(long n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 2;
        if (n == 2)
            return 6;
        if (n == 3)
            return 12;
        if (sCache.containsKey(n))
            return sCache.get(n);
        long res = 0;
        if (n % 2 == 0) {
            long m = n / 2;
            res = 3L * sCount(m) + sCount(m + 1) - 8L;
        } else {
            long m = n / 2;
            res = 4L * sCount(m) + 3L * pCount(m + 1) - 8L;
        }
        sCache.put(n, res);
        return res;
    }

    static long countUpto(long len) {
        if (len <= 0)
            return 0;
        return sCount(len) / 2L;
    }

    static long findLengthForIndex(long n) {
        long lo = 1;
        long hi = 1;
        while (countUpto(hi) < n)
            hi *= 2L;
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2L;
            if (countUpto(mid) >= n)
                hi = mid;
            else
                lo = mid + 1L;
        }
        return lo;
    }

    static class Node {
        static final int EMPTY = 0;
        static final int LEAF = 1;
        static final int CONCAT = 2;
        static final int MU = 3;

        int type = EMPTY;
        int left = -1;
        int right = -1;
        int child = -1;
        String bits = "";
        long len = 0;
        int first = -1;
        int last = -1;
    }

    static class WordBuilder {
        long mod;
        int maxI;
        long[] base;
        Map<Long, long[]>[] powSumCache;

        List<Node> nodes;
        List<long[]> evalCache;

        Map<Long, Integer> prefixCache;
        Map<Long, Integer> suffixCache;
        Map<Long, Integer> middleCache;

        int emptyId = 0;
        int leaf0Id = 0;
        int leaf1Id = 0;

        @SuppressWarnings("unchecked")
        WordBuilder(long mod, int maxI) {
            this.mod = mod;
            this.maxI = maxI;
            base = new long[maxI + 2];
            base[0] = 2L % mod;
            for (int i = 1; i < base.length; i++) {
                base[i] = (base[i - 1] * base[i - 1]) % mod;
            }

            powSumCache = new Map[base.length];
            for (int i = 0; i < base.length; i++)
                powSumCache[i] = new HashMap<>();

            nodes = new ArrayList<>(512);
            evalCache = new ArrayList<>(512);

            prefixCache = new HashMap<>();
            suffixCache = new HashMap<>();
            middleCache = new HashMap<>();

            Node empty = new Node();
            empty.type = Node.EMPTY;
            empty.len = 0;
            nodes.add(empty);
            evalCache.add(null);
            emptyId = 0;

            Node leaf0 = new Node();
            leaf0.type = Node.LEAF;
            leaf0.bits = "0";
            leaf0.len = 1;
            leaf0.first = 0;
            leaf0.last = 0;
            nodes.add(leaf0);
            evalCache.add(null);
            leaf0Id = nodes.size() - 1;

            Node leaf1 = new Node();
            leaf1.type = Node.LEAF;
            leaf1.bits = "1";
            leaf1.len = 1;
            leaf1.first = 1;
            leaf1.last = 1;
            nodes.add(leaf1);
            evalCache.add(null);
            leaf1Id = nodes.size() - 1;
        }

        long mulMod(long a, long b) {
            return (a * b) % mod;
        }

        int makeLeaf(String bits) {
            if (bits.isEmpty())
                return emptyId;
            if (bits.length() == 1)
                return bits.equals("0") ? leaf0Id : leaf1Id;
            Node node = new Node();
            node.type = Node.LEAF;
            node.bits = bits;
            node.len = bits.length();
            node.first = bits.charAt(0) - '0';
            node.last = bits.charAt(bits.length() - 1) - '0';
            nodes.add(node);
            evalCache.add(null);
            return nodes.size() - 1;
        }

        int makeBit(int b) {
            return b == 0 ? leaf0Id : leaf1Id;
        }

        int makeConcat(int left, int right) {
            if (nodes.get(left).len == 0)
                return right;
            if (nodes.get(right).len == 0)
                return left;
            Node node = new Node();
            node.type = Node.CONCAT;
            node.left = left;
            node.right = right;
            node.len = nodes.get(left).len + nodes.get(right).len;
            node.first = nodes.get(left).len > 0 ? nodes.get(left).first : nodes.get(right).first;
            node.last = nodes.get(right).len > 0 ? nodes.get(right).last : nodes.get(left).last;
            nodes.add(node);
            evalCache.add(null);
            return nodes.size() - 1;
        }

        int makeMu(int child) {
            if (nodes.get(child).len == 0)
                return emptyId;
            Node node = new Node();
            node.type = Node.MU;
            node.child = child;
            node.len = nodes.get(child).len * 2L;
            node.first = nodes.get(child).first;
            node.last = 1 - nodes.get(child).last;
            nodes.add(node);
            evalCache.add(null);
            return nodes.size() - 1;
        }

        int prefix(int nodeId) {
            Node node = nodes.get(nodeId);
            if (node.len <= 1)
                return emptyId;
            long key = ((long) nodeId << 2) | 0L;
            if (prefixCache.containsKey(key))
                return prefixCache.get(key);
            int res = emptyId;
            if (node.type == Node.LEAF) {
                res = makeLeaf(node.bits.substring(0, (int) (node.len - 1)));
            } else if (node.type == Node.CONCAT) {
                Node right = nodes.get(node.right);
                if (right.len > 1) {
                    res = makeConcat(node.left, prefix(node.right));
                } else if (right.len == 1) {
                    res = node.left;
                } else {
                    res = prefix(node.left);
                }
            } else if (node.type == Node.MU) {
                int p = prefix(node.child);
                int muP = makeMu(p);
                int bit = makeBit(nodes.get(node.child).last);
                res = makeConcat(muP, bit);
            }
            prefixCache.put(key, res);
            return res;
        }

        int suffix(int nodeId) {
            Node node = nodes.get(nodeId);
            if (node.len <= 1)
                return emptyId;
            long key = ((long) nodeId << 2) | 1L;
            if (suffixCache.containsKey(key))
                return suffixCache.get(key);
            int res = emptyId;
            if (node.type == Node.LEAF) {
                res = makeLeaf(node.bits.substring(1));
            } else if (node.type == Node.CONCAT) {
                Node left = nodes.get(node.left);
                if (left.len > 1) {
                    res = makeConcat(suffix(node.left), node.right);
                } else if (left.len == 1) {
                    res = node.right;
                } else {
                    res = suffix(node.right);
                }
            } else if (node.type == Node.MU) {
                int s = suffix(node.child);
                int muS = makeMu(s);
                int bit = makeBit(1 - nodes.get(node.child).first);
                res = makeConcat(bit, muS);
            }
            suffixCache.put(key, res);
            return res;
        }

        int middle(int nodeId) {
            Node node = nodes.get(nodeId);
            if (node.len <= 2)
                return emptyId;
            long key = ((long) nodeId << 2) | 2L;
            if (middleCache.containsKey(key))
                return middleCache.get(key);
            int res = emptyId;
            if (node.type == Node.LEAF) {
                res = makeLeaf(node.bits.substring(1, (int) (node.len - 1)));
            } else if (node.type == Node.CONCAT) {
                int tmp = suffix(nodeId);
                res = prefix(tmp);
            } else if (node.type == Node.MU) {
                int m = middle(node.child);
                int muM = makeMu(m);
                int bitLeft = makeBit(1 - nodes.get(node.child).first);
                int bitRight = makeBit(nodes.get(node.child).last);
                res = makeConcat(bitLeft, makeConcat(muM, bitRight));
            }
            middleCache.put(key, res);
            return res;
        }

        int oddEvenMap(int ancestor) {
            int mid = middle(ancestor);
            int muMid = makeMu(mid);
            int bitLeft = makeBit(1 - nodes.get(ancestor).first);
            int bitRight = makeBit(nodes.get(ancestor).last);
            return makeConcat(bitLeft, makeConcat(muMid, bitRight));
        }

        int oddOddMap(int ancestor) {
            int suf = suffix(ancestor);
            int muSuf = makeMu(suf);
            int bitLeft = makeBit(1 - nodes.get(ancestor).first);
            return makeConcat(bitLeft, muSuf);
        }

        int evenOddMap(int ancestor) {
            int pref = prefix(ancestor);
            int muPref = makeMu(pref);
            int bitRight = makeBit(nodes.get(ancestor).last);
            return makeConcat(muPref, bitRight);
        }

        long[] powSum(int i, long len) {
            Map<Long, long[]> cache = powSumCache[i];
            if (cache.containsKey(len))
                return cache.get(len);
            long[] res = new long[2];
            if (len == 0) {
                res[0] = 1L % mod;
                res[1] = 0;
            } else if (len == 1) {
                res[0] = base[i] % mod;
                res[1] = 1L % mod;
            } else if (len % 2 == 0) {
                long[] half = powSum(i, len / 2L);
                long p = half[0];
                long s = half[1];
                long p2 = mulMod(p, p);
                long s2 = mulMod(s, (p + 1L) % mod);
                res[0] = p2;
                res[1] = s2;
            } else {
                long[] prev = powSum(i, len - 1L);
                long p = prev[0];
                long s = prev[1];
                long p2 = mulMod(p, base[i]);
                long s2 = (s + p) % mod;
                res[0] = p2;
                res[1] = s2;
            }
            cache.put(len, res);
            return res;
        }

        long powBase(int i, long len) {
            return powSum(i, len)[0];
        }

        long sumGeom(int i, long len) {
            return powSum(i, len)[1];
        }

        long[] getEval(int nodeId) {
            long[] cached = evalCache.get(nodeId);
            if (cached != null)
                return cached;
            cached = new long[maxI + 2];
            evalCache.set(nodeId, cached);

            Node node = nodes.get(nodeId);
            if (node.len == 0)
                return cached;

            if (node.type == Node.LEAF) {
                for (int i = 0; i < cached.length; i++) {
                    long v = 0;
                    for (int c = 0; c < node.bits.length(); c++) {
                        v = (mulMod(v, base[i]) + (node.bits.charAt(c) - '0')) % mod;
                    }
                    cached[i] = v;
                }
            } else if (node.type == Node.CONCAT) {
                long[] leftEval = getEval(node.left);
                long[] rightEval = getEval(node.right);
                long lenR = nodes.get(node.right).len;
                for (int i = 0; i < cached.length; i++) {
                    long term = mulMod(leftEval[i], powBase(i, lenR));
                    cached[i] = (term + rightEval[i]) % mod;
                }
            } else if (node.type == Node.MU) {
                long[] childEval = getEval(node.child);
                long lenC = nodes.get(node.child).len;
                for (int i = 0; i < cached.length - 1; i++) {
                    long sumG = sumGeom(i + 1, lenC);
                    long factor = (base[i] + mod - 1L) % mod;
                    long term = mulMod(factor, childEval[i + 1]);
                    cached[i] = (sumG + term) % mod;
                }
            }
            return cached;
        }
    }

    static int selectNode(long len, long k, WordBuilder builder) {
        if (len <= 3) {
            return builder.makeLeaf(kBaseFactors[(int) len][(int) (k - 1L)]);
        }
        if (len % 2 == 0) {
            long n = len / 2L;
            long sizeO1 = pCount(n + 1L) / 2L;
            long sizeE = pCount(n);
            if (k <= sizeO1) {
                int ancestor = selectNode(n + 1L, pCount(n + 1L) / 2L + k, builder);
                return builder.oddEvenMap(ancestor);
            }
            if (k <= sizeO1 + sizeE) {
                int ancestor = selectNode(n, k - sizeO1, builder);
                return builder.makeMu(ancestor);
            }
            int ancestor = selectNode(n + 1L, k - sizeO1 - sizeE, builder);
            return builder.oddEvenMap(ancestor);
        } else {
            long n = len / 2L;
            long sizeO1 = pCount(n + 1L) / 2L;
            long sizeE = pCount(n + 1L);
            if (k <= sizeO1) {
                int ancestor = selectNode(n + 1L, pCount(n + 1L) / 2L + k, builder);
                return builder.oddOddMap(ancestor);
            }
            if (k <= sizeO1 + sizeE) {
                int ancestor = selectNode(n + 1L, k - sizeO1, builder);
                return builder.evenOddMap(ancestor);
            }
            int ancestor = selectNode(n + 1L, k - sizeO1 - sizeE, builder);
            return builder.oddOddMap(ancestor);
        }
    }

    static long computeAMod(long n) {
        if (n == 0)
            return 0;
        long len = findLengthForIndex(n);
        long prev = countUpto(len - 1L);
        long k = n - prev;
        long offset = pCount(len) / 2L + k;
        WordBuilder builder = new WordBuilder(MOD, 64);
        int root = selectNode(len, offset, builder);
        long[] vals = builder.getEval(root);
        return vals[0] % MOD;
    }

    static String solve() {
        long[] targets = new long[18];
        long v = 1;
        for (int i = 0; i < 18; i++) {
            v *= 10;
            targets[i] = v;
        }
        long sumMod = 0;
        for (long tgt : targets) {
            sumMod = (sumMod + computeAMod(tgt)) % MOD;
        }
        return String.format("%09d", sumMod);
    }

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