import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Collections;

public class Euler822 {

    static final long kMod = 1234567891L;

    static class Node {
        double logv;
        long modv;
        int id;

        Node(double logv, long modv, int id) {
            this.logv = logv;
            this.modv = modv;
            this.id = id;
        }
    }

    static long modPow(long base, long exp, long mod) {
        long res = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1L) == 1L) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1L;
        }
        return res;
    }

    static long S(long n, long m) {
        int len = (int) (n - 1);

        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node a, Node b) {
                if (a.logv != b.logv) {
                    return Double.compare(a.logv, b.logv);
                }
                return Integer.compare(a.id, b.id);
            }
        });

        double maxLog = 0.0;

        for (int i = 0; i < len; ++i) {
            long v = i + 2;
            Node node = new Node(Math.log(v), v % kMod, i);
            pq.add(node);
            if (node.logv > maxLog) {
                maxLog = node.logv;
            }
        }

        long steps = 0;
        while (steps < m) {
            Node x = pq.peek();
            if (2.0 * x.logv > maxLog) {
                break;
            }
            pq.poll();
            x.logv *= 2.0;
            x.modv = (x.modv * x.modv) % kMod;
            pq.add(x);
            if (x.logv > maxLog) {
                maxLog = x.logv;
            }
            ++steps;
        }

        ArrayList<Node> arr = new ArrayList<>(pq);

        if (steps == m) {
            long ans = 0;
            for (Node x : arr) {
                ans += x.modv;
                if (ans >= kMod) {
                    ans -= kMod;
                }
            }
            return ans;
        }

        Collections.sort(arr, new Comparator<Node>() {
            @Override
            public int compare(Node a, Node b) {
                if (a.logv != b.logv) {
                    return Double.compare(a.logv, b.logv);
                }
                return Integer.compare(a.id, b.id);
            }
        });

        long rem = m - steps;
        long q = rem / len;
        long r = rem % len;

        long expQ = modPow(2, q, kMod - 1);
        long expQ1 = (expQ * 2L) % (kMod - 1);

        long ans = 0;
        for (int i = 0; i < len; ++i) {
            long e = (i < r) ? expQ1 : expQ;
            long add = modPow(arr.get(i).modv, e, kMod);
            ans += add;
            if (ans >= kMod) {
                ans -= kMod;
            }
        }

        return ans;
    }

    public static String solve() {
        return Long.toString(S(10000, 10000000000000000L));
    }

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