import java.util.ArrayList;

public class Euler655 {

    static class ResidueEnumerator {
        int mod;
        int[] w;
        int[] nineW;
        int[] digits;
        int res;
        boolean done;

        ResidueEnumerator(int modValue, int[] weights) {
            this.mod = modValue;
            this.w = weights;
            nineW = new int[weights.length];
            digits = new int[weights.length];
            res = 0;
            done = false;
            for (int i = 0; i < w.length; ++i) {
                nineW[i] = (int) ((9L * w[i]) % mod);
            }
            if (w.length == 0)
                done = false;
        }

        boolean next(int[] out) {
            if (done)
                return false;
            out[0] = res;

            if (w.length == 0) {
                done = true;
                return true;
            }

            int p = 0;
            while (p < w.length) {
                if (digits[p] < 9) {
                    ++digits[p];
                    res += w[p];
                    if (res >= mod)
                        res -= mod;
                    return true;
                }
                digits[p] = 0;
                res -= nineW[p];
                if (res < 0)
                    res += mod;
                ++p;
            }

            done = true;
            return true;
        }
    }

    static long solveCase(int mod, int maxLen) {
        int[] pow10Mod = new int[maxLen];
        pow10Mod[0] = 1 % mod;
        for (int i = 1; i < maxLen; ++i) {
            pow10Mod[i] = (int) ((10L * pow10Mod[i - 1]) % mod);
        }

        int[] countRes = new int[mod];
        ArrayList<Integer> touched = new ArrayList<>(mod);
        ArrayList<Integer> restResidues = new ArrayList<>();

        long answer = 0;

        for (int len = 1; len <= maxLen; ++len) {
            int h = (len + 1) / 2;
            int split = (h + 1) / 2;

            int[] weight = new int[h];
            for (int i = 0; i < h; ++i) {
                int lo = i;
                int hi = len - 1 - i;
                if (lo == hi) {
                    weight[i] = pow10Mod[lo];
                } else {
                    int v = pow10Mod[lo] + pow10Mod[hi];
                    if (v >= mod)
                        v -= mod;
                    weight[i] = v;
                }
            }

            int leftW0 = weight[0];
            int[] leftRestW = new int[Math.max(0, split - 1)];
            for (int i = 1; i < split; ++i)
                leftRestW[i - 1] = weight[i];

            restResidues.clear();
            ResidueEnumerator enumRest = new ResidueEnumerator(mod, leftRestW);
            int[] r = new int[1];
            while (enumRest.next(r)) {
                restResidues.add(r[0]);
            }

            touched.clear();
            for (int lead = 1; lead <= 9; ++lead) {
                int leadContrib = (int) ((1L * lead * leftW0) % mod);
                for (int rr : restResidues) {
                    int v = leadContrib + rr;
                    if (v >= mod)
                        v -= mod;
                    if (countRes[v] == 0)
                        touched.add(v);
                    countRes[v]++;
                }
            }

            int[] rightW = new int[Math.max(0, h - split)];
            for (int i = split; i < h; ++i)
                rightW[i - split] = weight[i];

            long total = 0;
            ResidueEnumerator enumRight = new ResidueEnumerator(mod, rightW);
            while (enumRight.next(r)) {
                int rr = r[0];
                int need = (rr == 0) ? 0 : (mod - rr);
                total += countRes[need];
            }

            for (int idx : touched) {
                countRes[idx] = 0;
            }
            answer += total;
        }

        return answer;
    }

    public static String solve() {
        long ans = solveCase(10000019, 32);
        return Long.toString(ans);
    }

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