Problem 924: Larger Digit Permutation II

View on Project Euler

Project Euler Problem 924 Solution

EulerSolve provides an optimized solution for Project Euler Problem 924, Larger Digit Permutation II, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Define \(\operatorname{nextPerm}(m)\) to be the smallest integer strictly larger than \(m\) that uses exactly the same decimal digits as \(m\). If no larger rearrangement exists, its value is \(0\). The sequence in this problem is $$a_0=0,\qquad a_n=a_{n-1}^2+2,$$ and we must evaluate $$U(N)=\sum_{n=1}^{N}\operatorname{nextPerm}(a_n)\pmod{10^9+7},\qquad N=10^{16}.$$ The first terms are still small enough to inspect directly: $$a_1=2,\quad a_2=6,\quad a_3=38,\quad a_4=1446,\quad a_5=2090918,\quad a_6=4371938082726.$$ From that point on, the exact integers become far too large for direct decimal manipulation. The implementations therefore track only two finite-state shadows of the sequence: the residue \(a_n \bmod (10^9+7)\) and the final \(11\) decimal digits of \(a_n\). Mathematical Approach The solution is built around one problem-specific decomposition. For large \(n\), the next larger digit permutation of \(a_n\) is obtained by leaving the high decimal prefix alone and changing only the last \(11\) digits. That converts a huge decimal problem into the sum of a modular orbit and a fixed-width tail correction. Exact Prefix and the Turning Point at \(n=6\) The first five terms can be handled exactly....

Detailed mathematical approach

Problem Summary

Define \(\operatorname{nextPerm}(m)\) to be the smallest integer strictly larger than \(m\) that uses exactly the same decimal digits as \(m\). If no larger rearrangement exists, its value is \(0\). The sequence in this problem is

$$a_0=0,\qquad a_n=a_{n-1}^2+2,$$

and we must evaluate

$$U(N)=\sum_{n=1}^{N}\operatorname{nextPerm}(a_n)\pmod{10^9+7},\qquad N=10^{16}.$$

The first terms are still small enough to inspect directly:

$$a_1=2,\quad a_2=6,\quad a_3=38,\quad a_4=1446,\quad a_5=2090918,\quad a_6=4371938082726.$$

From that point on, the exact integers become far too large for direct decimal manipulation. The implementations therefore track only two finite-state shadows of the sequence: the residue \(a_n \bmod (10^9+7)\) and the final \(11\) decimal digits of \(a_n\).

Mathematical Approach

The solution is built around one problem-specific decomposition. For large \(n\), the next larger digit permutation of \(a_n\) is obtained by leaving the high decimal prefix alone and changing only the last \(11\) digits. That converts a huge decimal problem into the sum of a modular orbit and a fixed-width tail correction.

Exact Prefix and the Turning Point at \(n=6\)

The first five terms can be handled exactly. Their next larger digit permutations are

$$\operatorname{nextPerm}(2)=0,\qquad \operatorname{nextPerm}(6)=0,\qquad \operatorname{nextPerm}(38)=83,$$

$$\operatorname{nextPerm}(1446)=1464,\qquad \operatorname{nextPerm}(2090918)=2090981.$$

So the exact prefix contributes

$$U(5)=0+0+83+1464+2090981=2092528.$$

The real difficulty begins at \(a_6\). After that, the numbers are already too large to compute \(\operatorname{nextPerm}(a_n)\) by operating on the full decimal expansion for anything like \(10^{16}\) terms.

Two Finite-State Projections of the Recurrence

Let

$$p=10^9+7,\qquad a_n=10^{11}q_n+t_n,\qquad 0\le t_n<10^{11}.$$

Here \(t_n\) is treated as an \(11\)-digit decimal word, with leading zeros when necessary. This is important because next permutation is a positional digit operation, so those leading zeros still occupy digit slots.

Define

$$x_n\equiv a_n\pmod p.$$

Then the recurrence immediately gives

$$x_{n+1}\equiv x_n^2+2\pmod p,\qquad t_{n+1}\equiv t_n^2+2\pmod{10^{11}}.$$

The padded tail at the cutoff point is

$$t_5=00002090918.$$

So beyond the exact prefix, all arithmetic can be advanced inside the finite rings modulo \(p\) and modulo \(10^{11}\).

The 11-Digit Tail Correction

For the orbit relevant to this problem, the implementations exploit the invariant that from \(n\ge 6\) onward, the standard next-permutation pivot, swap, and suffix reversal all occur inside the last \(11\) decimal positions. If \(\operatorname{nextPerm}_{11}(t)\) denotes the next lexicographic permutation of the \(11\)-digit word \(t\), define

$$\Delta(t)=\operatorname{nextPerm}_{11}(t)-t.$$

Under that invariant,

$$\operatorname{nextPerm}(a_n)=10^{11}q_n+\operatorname{nextPerm}_{11}(t_n)=a_n+\Delta(t_n)\qquad (n\ge 6).$$

Therefore

$$\operatorname{nextPerm}(a_n)\equiv x_n+\Delta(t_n)\pmod p.$$

This is the decisive simplification: the huge decimal rearrangement is replaced by a modular term \(x_n\) and a small fixed-width correction. The C++ implementation checks this identity against exact big-integer values for \(n=6,\dots,15\), and the full tail sweep confirms that every visited \(11\)-digit tail on the relevant orbit has a valid next lexicographic rearrangement.

Decomposing the Full Sum

Let

$$S_{\text{small}}(N)=\sum_{n=1}^{\min\{N,5\}}\operatorname{nextPerm}(a_n).$$

Then for \(N\ge 6\),

$$U(N)\equiv S_{\text{small}}(N)+\sum_{n=6}^{N}x_n+\sum_{n=6}^{N}\Delta(t_n)\pmod p.$$

So after the first five terms, the task splits into two separate long sums: one over the orbit modulo \(p\), and one over the tail correction along the orbit modulo \(10^{11}\).

Eventually Periodic Orbit Modulo \(10^9+7\)

The map \(x\mapsto x^2+2 \pmod p\) acts on a finite state space, so the orbit starting from \(x_0=0\) is eventually periodic. The implementations find

$$\mu=39911,\qquad \lambda=21353,$$

where \(\mu\) is the preperiod length and \(\lambda\) is the cycle length. If

$$P(n)=\sum_{k=0}^{n}x_k,\qquad C=\sum_{j=0}^{\lambda-1}x_{\mu+j},$$

then for every \(n\ge \mu\), with

$$r=(n-\mu+1)\bmod\lambda,$$

we get

$$P(n)\equiv P(\mu-1)+\left\lfloor\frac{n-\mu+1}{\lambda}\right\rfloor C+\sum_{j=0}^{r-1}x_{\mu+j}\pmod p.$$

That turns \(\sum_{n=6}^{N}x_n\) into a prefix-sum query on one precomputed orbit.

The Full Tail Orbit Modulo \(10^{11}\)

The tail sequence also lives in a finite state space. Starting from \(t_5=00002090918\), the implementations iterate

$$t_{n+1}\equiv t_n^2+2\pmod{10^{11}}$$

and use the fact that the relevant orbit has length

$$L_{\text{tail}}=15625000=8\cdot 5^9.$$

After exactly \(L_{\text{tail}}\) steps, the tail returns to \(t_5\). If

$$D=\sum_{i=0}^{L_{\text{tail}}-1}\Delta(t_{6+i})\pmod p,$$

and

$$Q=\left\lfloor\frac{N-5}{L_{\text{tail}}}\right\rfloor,\qquad R=(N-5)\bmod L_{\text{tail}},$$

then

$$\sum_{n=6}^{N}\Delta(t_n)\equiv QD+\sum_{i=0}^{R-1}\Delta(t_{6+i})\pmod p.$$

This is the second compression step: a sum over almost \(10^{16}\) indices collapses to one full-cycle sum and one remainder sum.

Worked Example: the First Large Term

The transition from \(a_5\) to \(a_6\) shows the mechanism clearly. We have

$$a_5=2090918,\qquad \operatorname{nextPerm}(a_5)=2090981,$$

and then

$$a_6=a_5^2+2=4371938082726.$$

Its \(11\)-digit tail is

$$t_6=71938082726.$$

The next lexicographic permutation of this \(11\)-digit word is

$$71938082726\to 71938082762,$$

so

$$\Delta(t_6)=71938082762-71938082726=36.$$

Therefore

$$\operatorname{nextPerm}(a_6)=a_6+36=4371938082762.$$

This is exactly the same local correction rule later reused for every large term. As a further checkpoint, the exact prefix plus the first five large-regime terms satisfy

$$U(10)\equiv 543870437\pmod p.$$

How the Code Works

Exact Prefix and Residue Orbit

The C++, Python, and Java implementations first compute the exact contributions for \(n=1,\dots,5\), because those numbers are still small enough for direct decimal next-permutation arithmetic. They then build the orbit of \(x_{n+1}=x_n^2+2\pmod p\), stop when the first repeated state appears, and store prefix sums so that any interval sum of the residue sequence can be answered in constant additional time.

Tail Sweep and Quotient-Remainder Expansion

Next, the implementation starts from the padded tail \(00002090918\), advances the recurrence modulo \(10^{11}\), computes the \(11\)-digit next-permutation delta at each step, and accumulates one full orbit sum \(D\). A quotient-remainder split then expands that one-cycle total to all indices from \(n=6\) up to \(n=10^{16}\).

Consistency Checks

The C++ implementation also performs explicit validations. It checks the exact value of \(U(10)\), compares the decomposition against exact big-integer values for the early large terms, and verifies that the tail returns to its starting point after exactly \(L_{\text{tail}}\) steps. The Python and Java implementations follow the same mathematical decomposition but omit those explicit assertions.

Complexity Analysis

The orbit modulo \(p\) stores \(\mu+\lambda=61264\) states, so that phase costs \(O(\mu+\lambda)\) time and memory. The dominant work is the single sweep over the tail orbit of length \(L_{\text{tail}}=15625000\), plus at most one shorter remainder sweep. Hence the overall complexity is

$$O(\mu+\lambda+L_{\text{tail}})$$

time and

$$O(\mu+\lambda)$$

memory.

The gain is dramatic: the method never tries to materialize \(a_n\) for \(n\) anywhere near \(10^{16}\), and it never runs decimal next-permutation logic on astronomically large integers.

Footnotes and References

  1. Project Euler problem page: https://projecteuler.net/problem=924
  2. Lexicographic next permutation: Wikipedia - Permutation generation in lexicographic order
  3. Cycle detection in finite state spaces: Wikipedia - Cycle detection
  4. Modular arithmetic: Wikipedia - Modular arithmetic
  5. Recurrence relations: Wikipedia - Recurrence relation

Problem 924 source code

C++

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

#include <boost/multiprecision/cpp_int.hpp>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;
using boost::multiprecision::cpp_int;

constexpr u64 kMod = 1'000'000'007ULL;
constexpr u64 kTailMod = 100'000'000'000ULL;
constexpr u64 kTailCycleLen = 15'625'000ULL;  // 8 * 5^9
constexpr u64 kTargetN = 10'000'000'000'000'000ULL;

u64 add_mod(u64 x, u64 y) {
    x += y;
    if (x >= kMod) {
        x -= kMod;
    }
    return x;
}

u64 sub_mod(u64 x, u64 y) {
    return x >= y ? x - y : x + kMod - y;
}

u64 mul_mod(u64 x, u64 y, u64 mod) {
    return static_cast<u64>((static_cast<u128>(x) * y) % mod);
}

u64 step_mod(u64 x, u64 mod) {
    return (mul_mod(x, x, mod) + 2ULL) % mod;
}

u64 next_permutation_u64(u64 n) {
    std::string s = std::to_string(n);
    int i = static_cast<int>(s.size()) - 2;
    while (i >= 0 && s[i] >= s[i + 1]) {
        --i;
    }
    if (i < 0) {
        return 0;
    }
    int j = static_cast<int>(s.size()) - 1;
    while (s[j] <= s[i]) {
        --j;
    }
    std::swap(s[i], s[j]);
    std::reverse(s.begin() + i + 1, s.end());
    return static_cast<u64>(std::stoull(s));
}

std::pair<bool, u64> next_perm_delta_11(u64 tail) {
    std::array<int, 11> d{};
    u64 x = tail;
    for (int i = 10; i >= 0; --i) {
        d[i] = static_cast<int>(x % 10ULL);
        x /= 10ULL;
    }

    int i = 9;
    while (i >= 0 && d[i] >= d[i + 1]) {
        --i;
    }
    if (i < 0) {
        return {false, 0};
    }

    int j = 10;
    while (d[j] <= d[i]) {
        --j;
    }
    std::swap(d[i], d[j]);
    std::reverse(d.begin() + i + 1, d.end());

    u64 next_tail = 0;
    for (int digit : d) {
        next_tail = next_tail * 10ULL + static_cast<u64>(digit);
    }
    return {true, next_tail - tail};
}

cpp_int next_permutation_cpp(const cpp_int& value) {
    std::string s = value.convert_to<std::string>();
    int i = static_cast<int>(s.size()) - 2;
    while (i >= 0 && s[i] >= s[i + 1]) {
        --i;
    }
    if (i < 0) {
        return 0;
    }
    int j = static_cast<int>(s.size()) - 1;
    while (s[j] <= s[i]) {
        --j;
    }
    std::swap(s[i], s[j]);
    std::reverse(s.begin() + i + 1, s.end());
    return cpp_int(s);
}

u64 brute_u_mod(int n_limit) {
    cpp_int a = 0;
    cpp_int total = 0;
    for (int n = 1; n <= n_limit; ++n) {
        a = a * a + 2;
        total += next_permutation_cpp(a);
    }
    return static_cast<u64>(total % kMod);
}

struct CycleData {
    u64 mu = 0;
    u64 lambda = 0;
    std::vector<u64> values;
    std::vector<u64> pref_mod;
};

CycleData build_cycle_mod_p() {
    CycleData data;
    std::unordered_map<u64, u64> seen;
    seen.reserve(70000);
    seen.max_load_factor(0.7f);

    u64 x = 0;
    seen.emplace(x, 0);
    data.values.push_back(x);

    for (u64 idx = 1;; ++idx) {
        x = step_mod(x, kMod);
        auto it = seen.find(x);
        if (it != seen.end()) {
            data.mu = it->second;
            data.lambda = idx - it->second;
            break;
        }
        seen.emplace(x, idx);
        data.values.push_back(x);
    }

    data.pref_mod.assign(data.values.size() + 1, 0);
    for (std::size_t i = 0; i < data.values.size(); ++i) {
        data.pref_mod[i + 1] = add_mod(data.pref_mod[i], data.values[i]);
    }
    return data;
}

u64 prefix_sum_cycle(const CycleData& data, u64 n) {
    if (n + 1 <= data.values.size()) {
        return data.pref_mod[static_cast<std::size_t>(n + 1)];
    }

    const u64 mu = data.mu;
    const u64 lambda = data.lambda;
    const u64 sum_mu = data.pref_mod[static_cast<std::size_t>(mu)];
    const u64 cycle_sum = sub_mod(data.pref_mod[static_cast<std::size_t>(mu + lambda)],
                                  data.pref_mod[static_cast<std::size_t>(mu)]);

    const u64 remaining = n - mu + 1;
    const u64 full_cycles = remaining / lambda;
    const u64 rem = remaining % lambda;

    u64 total = sum_mu;
    total = add_mod(total, mul_mod(full_cycles % kMod, cycle_sum, kMod));
    const u64 partial = sub_mod(data.pref_mod[static_cast<std::size_t>(mu + rem)],
                                data.pref_mod[static_cast<std::size_t>(mu)]);
    total = add_mod(total, partial);
    return total;
}

u64 range_sum_cycle(const CycleData& data, u64 left, u64 right) {
    if (right < left) {
        return 0;
    }
    const u64 pref_r = prefix_sum_cycle(data, right);
    const u64 pref_l = (left == 0 ? 0 : prefix_sum_cycle(data, left - 1));
    return sub_mod(pref_r, pref_l);
}

u64 sum_small_exact(u64 n_limit) {
    u64 total = 0;
    u64 a = 0;
    const u64 upto = std::min<u64>(n_limit, 5);
    for (u64 n = 1; n <= upto; ++n) {
        a = a * a + 2;
        total = add_mod(total, next_permutation_u64(a) % kMod);
    }
    return total;
}

u64 sum_a_terms(u64 n_limit, const CycleData& mod_p_cycle) {
    if (n_limit < 6) {
        return 0;
    }
    return range_sum_cycle(mod_p_cycle, 6, n_limit);
}

u64 sum_delta_terms(u64 n_limit) {
    if (n_limit < 6) {
        return 0;
    }

    u64 a5_tail = 0;
    for (int i = 0; i < 5; ++i) {
        a5_tail = step_mod(a5_tail, kTailMod);
    }

    const u64 count = n_limit - 5;
    u64 cycle_sum = 0;
    u64 tail = a5_tail;

    for (u64 i = 0; i < kTailCycleLen; ++i) {
        tail = step_mod(tail, kTailMod);  // n = 6 + i
        const auto [ok, delta] = next_perm_delta_11(tail);
        assert(ok);
        cycle_sum = add_mod(cycle_sum, delta % kMod);
    }
    assert(tail == a5_tail);

    const u64 full_cycles = count / kTailCycleLen;
    const u64 rem = count % kTailCycleLen;

    u64 total = mul_mod(full_cycles % kMod, cycle_sum, kMod);

    tail = a5_tail;
    for (u64 i = 0; i < rem; ++i) {
        tail = step_mod(tail, kTailMod);
        const auto [ok, delta] = next_perm_delta_11(tail);
        assert(ok);
        total = add_mod(total, delta % kMod);
    }

    return total;
}

u64 solve(u64 n_limit) {
    const CycleData mod_p_cycle = build_cycle_mod_p();
    u64 answer = 0;
    answer = add_mod(answer, sum_small_exact(n_limit));
    answer = add_mod(answer, sum_a_terms(n_limit, mod_p_cycle));
    answer = add_mod(answer, sum_delta_terms(n_limit));
    return answer;
}

void validate() {
    assert(brute_u_mod(10) == 543870437ULL);

    u64 a_mod = 0;
    u64 a_tail = 0;
    cpp_int a_exact = 0;
    for (int n = 1; n <= 15; ++n) {
        a_mod = step_mod(a_mod, kMod);
        a_tail = step_mod(a_tail, kTailMod);
        a_exact = a_exact * a_exact + 2;

        const u64 exact_b_mod = static_cast<u64>(next_permutation_cpp(a_exact) % kMod);
        if (n <= 5) {
            assert(exact_b_mod == next_permutation_u64(static_cast<u64>(a_exact)) % kMod);
        } else {
            const auto [ok, delta] = next_perm_delta_11(a_tail);
            assert(ok);
            assert(exact_b_mod == add_mod(a_mod, delta % kMod));
        }
    }
}

}  // namespace

int main() {
    validate();
    std::cout << solve(kTargetN) << '\n';
    return 0;
}

Python

def solve():
    MOD = 1000000007; TAIL_MOD = 100000000000; TAIL_CL = 15625000; N = 10000000000000000

    def am(x, y):
        x += y; return x - MOD if x >= MOD else x
    def sm(x, y): return x - y if x >= y else x + MOD - y
    def mm(x, y, m): return x * y % m
    def step(x, m): return (x * x + 2) % m

    def next_perm_u64(n):
        s = list(str(n)); i = len(s)-2
        while i >= 0 and s[i] >= s[i+1]: i -= 1
        if i < 0: return 0
        j = len(s)-1
        while s[j] <= s[i]: j -= 1
        s[i], s[j] = s[j], s[i]; s[i+1:] = s[i+1:][::-1]
        return int(''.join(s))

    def next_perm_delta_11(tail):
        d = []; x = tail
        for i in range(11): d.append(x % 10); x //= 10
        d.reverse()
        i = 9
        while i >= 0 and d[i] >= d[i+1]: i -= 1
        if i < 0: return False, 0
        j = 10
        while d[j] <= d[i]: j -= 1
        d[i], d[j] = d[j], d[i]; d[i+1:] = d[i+1:][::-1]
        nt = 0
        for dig in d: nt = nt*10 + dig
        return True, nt - tail

    # Build cycle for a mod MOD
    seen = {}; vals = [0]; x = 0; seen[x] = 0
    idx = 1
    while True:
        x = step(x, MOD)
        if x in seen: mu = seen[x]; lam = idx - mu; break
        seen[x] = idx; vals.append(x); idx += 1
    pref = [0]*(len(vals)+1)
    for i in range(len(vals)): pref[i+1] = am(pref[i], vals[i])

    def prefix_sum(n):
        if n + 1 <= len(vals): return pref[n+1]
        sm_val = pref[mu]; cs = sm(pref[mu+lam], pref[mu])
        rem = n - mu + 1; fc = rem // lam; r = rem % lam
        total = sm_val; total = am(total, mm(fc % MOD, cs, MOD))
        total = am(total, sm(pref[mu+r], pref[mu]))
        return total

    def range_sum(l, r):
        pr = prefix_sum(r); pl = prefix_sum(l-1) if l > 0 else 0
        return sm(pr, pl)

    # Small exact (n=1..5)
    ans = 0; a = 0
    for n in range(1, min(N, 5)+1):
        a = a*a + 2
        ans = am(ans, next_perm_u64(a) % MOD)

    if N >= 6:
        ans = am(ans, range_sum(6, N))  # sum of a_n mod MOD

    # Delta terms
    if N >= 6:
        a5t = 0
        for _ in range(5): a5t = step(a5t, TAIL_MOD)
        count = N - 5; cycle_sum = 0; tail = a5t
        for _ in range(TAIL_CL):
            tail = step(tail, TAIL_MOD)
            ok, delta = next_perm_delta_11(tail)
            cycle_sum = am(cycle_sum, delta % MOD)
        fc = count // TAIL_CL; r = count % TAIL_CL
        dt = mm(fc % MOD, cycle_sum, MOD)
        tail = a5t
        for _ in range(r):
            tail = step(tail, TAIL_MOD)
            ok, delta = next_perm_delta_11(tail)
            dt = am(dt, delta % MOD)
        ans = am(ans, dt)

    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.math.BigInteger;
import java.util.*;

public class Euler924 {

    static final long kMod = 1000000007L;
    static final long kTailMod = 100000000000L;
    static final long kTailCycleLen = 15625000L;
    static final long kTargetN = 10000000000000000L;

    static long stepMod(long x, long mod) {
        if (mod == kMod) {
            return (x * x + 2) % mod;
        } else {
            BigInteger bigX = BigInteger.valueOf(x);
            return bigX.multiply(bigX).add(BigInteger.valueOf(2)).remainder(BigInteger.valueOf(mod)).longValue();
        }
    }

    static class CycleData {
        long mu = 0;
        long lambda_ = 0;
        List<Long> values = new ArrayList<>();
        List<Long> prefMod = new ArrayList<>();
    }

    static CycleData buildCycleModP() {
        CycleData data = new CycleData();
        Map<Long, Long> seen = new HashMap<>();
        long x = 0;
        seen.put(x, 0L);
        data.values.add(x);

        long idx = 1;
        while (true) {
            x = stepMod(x, kMod);
            if (seen.containsKey(x)) {
                data.mu = seen.get(x);
                data.lambda_ = idx - seen.get(x);
                break;
            }
            seen.put(x, idx);
            data.values.add(x);
            idx++;
        }

        data.prefMod = new ArrayList<>(Collections.nCopies(data.values.size() + 1, 0L));
        for (int i = 0; i < data.values.size(); i++) {
            data.prefMod.set(i + 1, (data.prefMod.get(i) + data.values.get(i)) % kMod);
        }
        return data;
    }

    static long prefixSumCycle(CycleData data, long n) {
        if (n + 1 <= data.values.size()) {
            return data.prefMod.get((int) (n + 1));
        }

        long mu = data.mu;
        long lambda_ = data.lambda_;
        long sumMu = data.prefMod.get((int) mu);
        long cycleSum = (data.prefMod.get((int) (mu + lambda_)) - data.prefMod.get((int) mu) + kMod) % kMod;

        long remaining = n - mu + 1;
        long fullCycles = remaining / lambda_;
        long rem = remaining % lambda_;

        long total = sumMu;
        total = (total + (fullCycles % kMod) * cycleSum) % kMod;
        long partial = (data.prefMod.get((int) (mu + rem)) - data.prefMod.get((int) mu) + kMod) % kMod;
        total = (total + partial) % kMod;
        return total;
    }

    static long rangeSumCycle(CycleData data, long left, long right) {
        if (right < left)
            return 0;
        long prefR = prefixSumCycle(data, right);
        long prefL = left == 0 ? 0 : prefixSumCycle(data, left - 1);
        return (prefR - prefL + kMod) % kMod;
    }

    static boolean nextPermutation(char[] array) {
        int i = array.length - 2;
        while (i >= 0 && array[i] >= array[i + 1]) {
            i--;
        }
        if (i < 0)
            return false;

        int j = array.length - 1;
        while (array[j] <= array[i]) {
            j--;
        }

        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;

        for (int l = i + 1, r = array.length - 1; l < r; l++, r--) {
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;
        }
        return true;
    }

    static long sumSmallExact(long n_limit) {
        long total = 0;
        BigInteger a = BigInteger.ZERO;
        long upto = Math.min(n_limit, 5L);
        for (int i = 0; i < upto; i++) {
            a = a.multiply(a).add(BigInteger.valueOf(2));
            char[] s = a.toString().toCharArray();
            if (nextPermutation(s)) {
                BigInteger val = new BigInteger(new String(s));
                total = (total + val.remainder(BigInteger.valueOf(kMod)).longValue()) % kMod;
            }
        }
        return total;
    }

    static long sumATerms(long n_limit, CycleData mod_p_cycle) {
        if (n_limit < 6)
            return 0;
        return rangeSumCycle(mod_p_cycle, 6, n_limit);
    }

    static class PermDelta {
        boolean ok;
        long delta;

        PermDelta(boolean ok, long delta) {
            this.ok = ok;
            this.delta = delta;
        }
    }

    static PermDelta nextPermDelta11(long tail) {
        char[] d = new char[11];
        long x = tail;
        for (int i = 10; i >= 0; i--) {
            d[i] = (char) ('0' + (x % 10));
            x /= 10;
        }

        if (!nextPermutation(d))
            return new PermDelta(false, 0);

        long nextTail = 0;
        for (int i = 0; i < 11; i++) {
            nextTail = nextTail * 10 + (d[i] - '0');
        }
        return new PermDelta(true, nextTail - tail);
    }

    static long sumDeltaTerms(long n_limit) {
        if (n_limit < 6)
            return 0;

        long a5Tail = 0;
        for (int i = 0; i < 5; i++) {
            a5Tail = stepMod(a5Tail, kTailMod);
        }

        long count = n_limit - 5;
        long cycleSum = 0;
        long tail = a5Tail;

        for (long i = 0; i < kTailCycleLen; i++) {
            tail = stepMod(tail, kTailMod);
            PermDelta pd = nextPermDelta11(tail);
            cycleSum = (cycleSum + pd.delta % kMod) % kMod;
        }

        long fullCycles = count / kTailCycleLen;
        long rem = count % kTailCycleLen;

        long total = ((fullCycles % kMod) * cycleSum) % kMod;

        tail = a5Tail;
        for (long i = 0; i < rem; i++) {
            tail = stepMod(tail, kTailMod);
            PermDelta pd = nextPermDelta11(tail);
            total = (total + pd.delta % kMod) % kMod;
        }

        return total;
    }

    public static String solve(long n_limit) {
        CycleData modPCycle = buildCycleModP();
        long answer = 0;
        answer = (answer + sumSmallExact(n_limit)) % kMod;
        answer = (answer + sumATerms(n_limit, modPCycle)) % kMod;
        answer = (answer + sumDeltaTerms(n_limit)) % kMod;
        return Long.toString(answer);
    }

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