public class Euler250 {
    static int powmodInt(int base, int exp, int mod) {
        int result = 1 % mod;
        int cur = base % mod;

        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = (int) (((long) result * cur) % mod);
            }
            cur = (int) (((long) cur * cur) % mod);
            exp >>= 1;
        }
        return result;
    }

    public static String solve() {
        int limit = 250250;
        int divisor = 250;
        long modulo = 10000000000000000L;

        long[] dp = new long[divisor];
        long[] next = new long[divisor];
        dp[0] = 1;

        for (int i = 1; i <= limit; ++i) {
            int residue = powmodInt(i, i, divisor);

            for (int r = 0; r < divisor; ++r) {
                next[r] = dp[r];
            }

            for (int r = 0; r < divisor; ++r) {
                if (dp[r] == 0)
                    continue;
                int to = (r + residue) % divisor;
                next[to] += dp[r];
                if (next[to] >= modulo) {
                    next[to] -= modulo;
                }
            }

            long[] temp = dp;
            dp = next;
            next = temp;
        }

        long allDivisible = dp[0];
        long ans = (allDivisible + modulo - 1) % modulo;
        return String.valueOf(ans);
    }

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