public class Euler605 {

    static long modPow(long a, long e, long mod) {
        long r = 1;
        long x = a % mod;
        while (e > 0) {
            if ((e & 1) == 1)
                r = (r * x) % mod;
            x = (x * x) % mod;
            e >>= 1;
        }
        return r;
    }

    public static String solve() {
        long MOD = 100000000L;
        long n = 100000007L;
        long k = 10007L;

        long two_n_mod = modPow(2, n, MOD);
        long two_nk_mod = modPow(2, n - k, MOD);
        long x_mod = (two_n_mod + MOD - 1) % MOD;

        long inner_mod = (((k - 1) * two_n_mod % MOD) + (n - k + 1)) % MOD;

        long ans = (two_nk_mod * inner_mod) % MOD;
        ans = (ans * x_mod) % MOD;
        ans = (ans * x_mod) % MOD;

        return String.format("%08d", ans);
    }

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