import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;

public class Euler835 {

    static final long kMod = 1234567891L;

    static long modMul(long a, long b) {
        return (a * b) % kMod;
    }

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

    static long sumFamilyIMod(long halfExp) {
        long sMod = modPow(10, halfExp);
        long inv2 = (kMod + 1) / 2;
        long inv3 = modPow(3, kMod - 2);
        long q = modMul(sMod, inv2);

        long part = q;
        part = modMul(part, (q + 1) % kMod);
        long fourQMinusOne = (modMul(4, q) + kMod - 1) % kMod;
        part = modMul(part, fourQMinusOne);
        part = modMul(part, inv3);

        part = (part + kMod - 2) % kMod;
        return part;
    }

    static long[][] matMul(long[][] A, long[][] B) {
        long[][] C = new long[3][3];
        for (int i = 0; i < 3; ++i) {
            for (int k = 0; k < 3; ++k) {
                if (A[i][k] == 0)
                    continue;
                for (int j = 0; j < 3; ++j) {
                    if (B[k][j] == 0)
                        continue;
                    C[i][j] = (C[i][j] + modMul(A[i][k], B[k][j])) % kMod;
                }
            }
        }
        return C;
    }

    static long[][] matPow(long[][] base, long exp) {
        long[][] res = new long[3][3];
        for (int i = 0; i < 3; ++i)
            res[i][i] = 1;
        while (exp > 0) {
            if ((exp & 1) == 1)
                res = matMul(res, base);
            base = matMul(base, base);
            exp >>= 1;
        }
        return res;
    }

    static long sumFamilyIIMod(long K) {
        if (K == 0)
            return 0;
        if (K == 1)
            return 12;

        long[][] A = new long[3][3];
        A[0][0] = 6;
        A[0][1] = kMod - 1;
        A[0][2] = 0;
        A[1][0] = 1;
        A[1][1] = 0;
        A[1][2] = 0;
        A[2][0] = 6;
        A[2][1] = kMod - 1;
        A[2][2] = 1;

        long[][] P = matPow(A, K - 2);
        long[] v = { 70, 12, 82 };
        long[] out = { 0, 0, 0 };

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                out[i] = (out[i] + modMul(P[i][j], v[j])) % kMod;
            }
        }

        return out[2];
    }

    static BigDecimal sqrt(BigDecimal A, final int SCALE) {
        BigDecimal x0 = new BigDecimal("0");
        BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
        while (!x0.equals(x1)) {
            x0 = x1;
            x1 = A.divide(x0, SCALE, RoundingMode.HALF_UP).add(x0)
                    .divide(new BigDecimal("2"), SCALE, RoundingMode.HALF_UP);
        }
        return x1;
    }

    // Since we only need logarithms we can compute log10 directly or just use
    // double for the integer part.
    // E = 10^10 so log10 calculations need enough precision to not make an
    // off-by-one error.
    // ~100 decimal places is enough. Let's use BigInteger/BigDecimal for high
    // precision root finding.
    // Note: K \approx 10^10 / log10(lambda)
    // Actually, we can use a known approximation or BigDecimal.
    // Java doesn't have Math.log10(BigDecimal). We can use a Taylor series or
    // Newton's method, or simply compute log(x) by using high precision double
    // since 10^10 isn't that large. Wait, double has 53 bits (15 digits). We need
    // more than 10 digits of log10(lambda) to get K exact. We need at least 15
    // digits. Double is borderline.
    // We can use BigDecimal for high precision constants.
    // lambda = 3 + 2 * sqrt(2) =
    // 5.828427124746190097603377448419396157139343750753896...
    // log10(lambda) = 0.765551370675727192892973719114704381335...
    // alpha = (70 - 12(3-2sqrt2)) / (8sqrt2) = (34 + 24sqrt2) / (8sqrt2) = 3 +
    // (17/4)sqrt2 = 3 + 4.25 * sqrt(2) = 9.01040764008565...
    // log10(alpha) = 0.954743209598287515...

    static long kMaxForPower10N(long exp10) {
        MathContext mc = new MathContext(100, RoundingMode.HALF_UP);
        BigDecimal sqrt2 = sqrt(new BigDecimal("2"), 100);
        BigDecimal lambda = new BigDecimal("3").add(new BigDecimal("2").multiply(sqrt2));
        BigDecimal mu = new BigDecimal("3").subtract(new BigDecimal("2").multiply(sqrt2));
        BigDecimal p1 = new BigDecimal("12");
        BigDecimal p2 = new BigDecimal("70");

        BigDecimal alpha = p2.subtract(p1.multiply(mu)).divide(lambda.multiply(lambda.subtract(mu)), mc);

        // We need to compute log10(lambda) and log10(alpha) to high precision.
        // We can cheat by using precalculated high precision values.
        BigDecimal log10Lambda = new BigDecimal("0.7655513706757271928929737191147043813350284560759086");
        BigDecimal log10Alpha = new BigDecimal("0.9547432095982875151520625345719335967272288304245084");

        BigDecimal E = new BigDecimal(exp10);
        BigDecimal kest = E.subtract(log10Alpha).divide(log10Lambda, mc);
        long K = kest.longValue();

        // evaluate log10_pk(K)
        BigDecimal log10pkK = new BigDecimal(K).multiply(log10Lambda).add(log10Alpha);
        BigDecimal log10pkKp1 = new BigDecimal(K + 1).multiply(log10Lambda).add(log10Alpha);

        while (log10pkKp1.compareTo(E) <= 0) {
            K++;
            log10pkKp1 = new BigDecimal(K + 1).multiply(log10Lambda).add(log10Alpha);
        }
        while (K > 0) {
            log10pkK = new BigDecimal(K).multiply(log10Lambda).add(log10Alpha);
            if (log10pkK.compareTo(E) <= 0)
                break;
            K--;
        }

        return K;
    }

    public static String solve() {
        long exp10 = 10000000000L;
        long K = kMaxForPower10N(exp10);

        long sumI = sumFamilyIMod(exp10 / 2);
        long sumII = sumFamilyIIMod(K);

        long ans = (sumI + sumII) % kMod;
        ans = (ans + kMod - 12) % kMod;

        return Long.toString(ans);
    }

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