public class Euler405 {
    private static final long kMod = 410338673L; // 17^7
    private static final long kPhi = 386201104L; // phi(17^7)

    private static long modPow(long base, long exp, long mod) {
        long result = 1 % mod;
        long cur = base % mod;
        long e = exp;
        while (e > 0) {
            if ((e & 1L) != 0L) {
                result = (result * cur) % mod;
            }
            cur = (cur * cur) % mod;
            e >>= 1L;
        }
        return result;
    }

    public static String solve() {
        long k = 1000000000000000000L;

        long nModPhi = modPow(10, k, kPhi);

        long inv3 = modPow(3, kPhi - 1, kMod);
        long inv5 = modPow(5, kPhi - 1, kMod);
        long inv15 = (inv3 * inv5) % kMod;

        long p2 = modPow(2, nModPhi, kMod);
        long p4 = modPow(4, nModPhi, kMod);

        long ans = 1L;
        ans = (ans + kMod - inv15) % kMod;
        ans = (ans + kMod - (((4L * p2) % kMod) * inv3) % kMod) % kMod;
        ans = (ans + (((2L * p4) % kMod) * inv5) % kMod) % kMod;

        return String.valueOf(ans);
    }

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