Problem 698: 123 Numbers

Project Euler Problem 698 Solution

EulerSolve provides an optimized solution for Project Euler Problem 698, 123 Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary A positive integer is called a 123-number if its decimal expansion uses only the digits $1$, $2$, and $3$, and every nonzero digit count is itself a 123-number. If $c_1(n)$, $c_2(n)$, and $c_3(n)$ denote the numbers of $1$'s, $2$'s, and $3$'s in $n$, then each positive value among those counts must again satisfy the same rule. The task is to locate the $N$-th such number in increasing order and report its value modulo $123123123$. Mathematical Approach The key observation is that a candidate number is determined by two layers of information: its total length and the triple of digit counts $(A,B,C)$. Once that triple is admissible, the number of corresponding decimal strings is a multinomial coefficient. The implementation therefore counts entire families of strings and jumps directly to the desired rank instead of enumerating all valid numbers one by one. Step 1: Define the recursive admissibility set Let $\mathcal{S}$ be the set of all positive integers that are valid as digit counts....

Detailed mathematical approach

Problem Summary

A positive integer is called a 123-number if its decimal expansion uses only the digits $1$, $2$, and $3$, and every nonzero digit count is itself a 123-number. If $c_1(n)$, $c_2(n)$, and $c_3(n)$ denote the numbers of $1$'s, $2$'s, and $3$'s in $n$, then each positive value among those counts must again satisfy the same rule. The task is to locate the $N$-th such number in increasing order and report its value modulo $123123123$.

Mathematical Approach

The key observation is that a candidate number is determined by two layers of information: its total length and the triple of digit counts $(A,B,C)$. Once that triple is admissible, the number of corresponding decimal strings is a multinomial coefficient. The implementation therefore counts entire families of strings and jumps directly to the desired rank instead of enumerating all valid numbers one by one.

Step 1: Define the recursive admissibility set

Let $\mathcal{S}$ be the set of all positive integers that are valid as digit counts. We start with

$$1 \in \mathcal{S}.$$

For $n>1$, membership means two things simultaneously:

$$n \in \mathcal{S} \iff \text{every digit of } n \text{ lies in } \{1,2,3\} \text{ and } \forall i \in \{1,2,3\},\ c_i(n)=0 \text{ or } c_i(n)\in\mathcal{S}.$$

This recursion is well founded because each count $c_i(n)$ is at most the number of digits of $n$, hence strictly smaller than $n$ for every $n>1$. So admissibility can be computed bottom-up: when testing $n$, all smaller count values are already known.

Step 2: Count valid strings of a fixed length

Fix a length $L$. Suppose the final string contains $A$ copies of digit $1$, $B$ copies of digit $2$, and $C$ copies of digit $3$. Then

$$A+B+C=L,$$

and the triple is admissible exactly when every nonzero member of $\{A,B,C\}$ lies in $\mathcal{S}$.

For one such admissible triple, the number of distinct strings is

$$M(L;A,B,C)=\frac{L!}{A!\,B!\,C!}=\binom{L}{A}\binom{L-A}{B}.$$

Therefore the total number of valid 123-numbers of length $L$ is

$$F(L)=\sum_{\substack{A+B+C=L\\A,B,C\ge 0\\A,B,C\in \mathcal{S}\cup\{0\}}} \binom{L}{A}\binom{L-A}{B}.$$

This reduces the fixed-length problem to a scan over admissible count triples rather than over all $3^L$ raw strings.

Step 3: Convert numeric order into length order plus lexicographic order

Every valid number with fewer digits is numerically smaller than every valid number with more digits. Inside one fixed length, ordinary lexicographic order agrees with numeric order because there are no leading zeros.

So the search proceeds in two stages. First find the unique length $L$ such that

$$\sum_{\ell=1}^{L-1} F(\ell) < N \le \sum_{\ell=1}^{L} F(\ell).$$

Then define the residual rank inside that length by

$$R=N-\sum_{\ell=1}^{L-1} F(\ell).$$

Now the task is purely combinatorial: find the $R$-th admissible length-$L$ string in lexicographic order.

Step 4: Count completions from a fixed prefix

Assume we have already fixed a prefix of length $p$, and that this prefix uses $p_1$ ones, $p_2$ twos, and $p_3$ threes. Let the remaining length be

$$r=L-p.$$

If the final count triple is $(A,B,C)$, then the suffix still needs

$$a=A-p_1,\qquad b=B-p_2,\qquad c=C-p_3,$$

with $a,b,c\ge 0$ and $a+b+c=r$. For this particular final triple, the number of admissible completions of the current prefix is

$$\frac{r!}{a!\,b!\,c!}=\binom{r}{a}\binom{r-a}{b}.$$

Summing over all admissible final triples gives the block size

$$G_L(p,p_1,p_2,p_3)=\sum_{\substack{A+B+C=L\\A,B,C\in \mathcal{S}\cup\{0\}\\A\ge p_1,\ B\ge p_2,\ C\ge p_3}} \binom{r}{A-p_1}\binom{r-(A-p_1)}{B-p_2}.$$

Testing the next digit in the order $1,2,3$ partitions all valid completions into consecutive lexicographic blocks. If the desired rank is larger than the first block, subtract that block and continue with the next digit; otherwise keep that digit and move to the next position.

Step 5: Worked example

The first admissible count values are

$$1,2,3,11,12,13,21,22,23,31,32,33,\dots$$

so $4\notin\mathcal{S}$. That immediately explains the early lengths. For $L=1,2,3$, every count triple uses only the values $0,1,2,3$, so every ternary string is valid and

$$F(1)=3,\qquad F(2)=9,\qquad F(3)=27.$$

The cumulative total through length $3$ is therefore

$$3+9+27=39.$$

Hence the $40$-th 123-number must be the first admissible string of length $4$. The lexicographically smallest candidate is $1111$, but its count triple is $(4,0,0)$, which is invalid because $4\notin\mathcal{S}$. The next candidate is $1112$, whose count triple is $(3,1,0)$; both positive counts $3$ and $1$ are admissible. Therefore the first valid length-$4$ string is $1112$, so the $40$-th 123-number is $1112$.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They first build a boolean table of admissible count values in increasing order, which resolves the recursive definition iteratively. Next they construct Pascal-triangle rows on demand, so every binomial coefficient needed for the multinomial formulas can be read in constant time afterward.

All counting is performed with saturation at $N+1$. This is enough because the search never needs an exact block size once that block is already larger than the remaining rank. After the admissibility table and binomial table are available, the implementation sums $F(1),F(2),\dots$ until it identifies the target length, then builds the answer one digit at a time by evaluating prefix-completion counts for tentative next digits $1$, $2$, and $3$.

When the final decimal string is known, the remainder modulo $123123123$ is evaluated left to right via

$$v_0=0,\qquad v_{k+1}\equiv 10v_k+d_{k+1}\pmod{123123123}.$$

This avoids ever converting the full answer into a large integer type.

Complexity Analysis

Let $M$ be the size of the admissibility table and $L$ the length of the target number. Building the admissibility table costs $O(M\log M)$ time because each candidate is scanned digit by digit, and it uses $O(M)$ memory. Growing Pascal rows up to length $L$ costs $O(L^2)$ time and memory.

To locate the correct length, the implementation evaluates $F(\ell)$ for $\ell=1,2,\dots,L$. Each such evaluation scans $O(\ell^2)$ count pairs, so the total cost is

$$\sum_{\ell=1}^{L} O(\ell^2)=O(L^3).$$

The unranking stage performs at most three prefix queries per position, and each query scans admissible final triples in $O(L^2)$, giving another $O(L^3)$ phase. Overall the method runs in

$$O(M\log M+L^3)$$

time and uses $O(M+L^2)$ memory for the target instance.

Footnotes and References

Problem page: https://projecteuler.net/problem=698
Multinomial coefficients: Wikipedia — Multinomial theorem
Binomial coefficients: Wikipedia — Binomial coefficient
Lexicographical order: Wikipedia — Lexicographical order
Dynamic programming: Wikipedia — Dynamic programming

Problem 698 source code

C++

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

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

constexpr u64 kTargetN = 111'111'111'111'222'333ULL;
constexpr u64 kMod = 123'123'123ULL;
constexpr int kIs123Limit = 5000;

u64 sat_add(const u64 a, const u64 b, const u64 cap) {
    const u128 v = static_cast<u128>(a) + static_cast<u128>(b);
    return (v > static_cast<u128>(cap)) ? (cap + 1U) : static_cast<u64>(v);
}

u64 sat_mul(const u64 a, const u64 b, const u64 cap) {
    const u128 v = static_cast<u128>(a) * static_cast<u128>(b);
    return (v > static_cast<u128>(cap)) ? (cap + 1U) : static_cast<u64>(v);
}

std::vector<std::uint8_t> build_is123(const int limit) {
    std::vector<std::uint8_t> is123(static_cast<std::size_t>(limit) + 1U, 0U);
    is123[1] = 1U;

    for (int x = 2; x <= limit; ++x) {
        std::string s = std::to_string(x);
        bool digits_ok = true;
        int c1 = 0;
        int c2 = 0;
        int c3 = 0;
        for (const char ch : s) {
            if (ch == '1') {
                ++c1;
            } else if (ch == '2') {
                ++c2;
            } else if (ch == '3') {
                ++c3;
            } else {
                digits_ok = false;
                break;
            }
        }
        if (!digits_ok) {
            continue;
        }

        if ((c1 == 0 || is123[static_cast<std::size_t>(c1)]) &&
            (c2 == 0 || is123[static_cast<std::size_t>(c2)]) &&
            (c3 == 0 || is123[static_cast<std::size_t>(c3)])) {
            is123[static_cast<std::size_t>(x)] = 1U;
        }
    }

    return is123;
}

class Nth123Solver {
   public:
    Nth123Solver(const u64 cap, const std::vector<std::uint8_t>& is123)
        : cap_(cap), is123_(is123), choose_(1, std::vector<u64>(1, 1U)) {}

    std::string solve(const u64 n) {
        u64 cumulative = 0;
        int length = 0;

        while (true) {
            ++length;
            const u64 count = count_length(length);
            if (sat_add(cumulative, count, cap_) >= n) {
                length_ = length;
                break;
            }
            cumulative += count;
        }

        u64 rank_in_length = n - cumulative;
        memo_.clear();

        int used1 = 0;
        int used2 = 0;
        int used3 = 0;
        std::string out;
        out.reserve(static_cast<std::size_t>(length_));

        for (int pos = 0; pos < length_; ++pos) {
            for (int d = 1; d <= 3; ++d) {
                int n1 = used1;
                int n2 = used2;
                int n3 = used3;
                if (d == 1) {
                    ++n1;
                } else if (d == 2) {
                    ++n2;
                } else {
                    ++n3;
                }

                const u64 cnt = count_with_prefix(pos + 1, n1, n2, n3);
                if (rank_in_length > cnt) {
                    rank_in_length -= cnt;
                } else {
                    out.push_back(static_cast<char>('0' + d));
                    used1 = n1;
                    used2 = n2;
                    used3 = n3;
                    break;
                }
            }
        }

        return out;
    }

   private:
    void ensure_choose(const int n) {
        while (static_cast<int>(choose_.size()) <= n) {
            const int m = static_cast<int>(choose_.size());
            choose_.push_back(std::vector<u64>(static_cast<std::size_t>(m) + 1U, 0U));
            choose_[static_cast<std::size_t>(m)][0] = 1U;
            choose_[static_cast<std::size_t>(m)][static_cast<std::size_t>(m)] = 1U;
            for (int k = 1; k < m; ++k) {
                const u64 left = choose_[static_cast<std::size_t>(m - 1)][static_cast<std::size_t>(k - 1)];
                const u64 right = choose_[static_cast<std::size_t>(m - 1)][static_cast<std::size_t>(k)];
                choose_[static_cast<std::size_t>(m)][static_cast<std::size_t>(k)] =
                    sat_add(left, right, cap_);
            }
        }
    }

    u64 multinomial(const int n, const int a, const int b) {
        ensure_choose(n);
        const u64 first = choose_[static_cast<std::size_t>(n)][static_cast<std::size_t>(a)];
        const u64 second = choose_[static_cast<std::size_t>(n - a)][static_cast<std::size_t>(b)];
        return sat_mul(first, second, cap_);
    }

    u64 count_length(const int length) {
        u64 total = 0;
        for (int a = 0; a <= length; ++a) {
            if (a > 0 && !is123_[static_cast<std::size_t>(a)]) {
                continue;
            }
            for (int b = 0; b + a <= length; ++b) {
                const int c = length - a - b;
                if (b > 0 && !is123_[static_cast<std::size_t>(b)]) {
                    continue;
                }
                if (c > 0 && !is123_[static_cast<std::size_t>(c)]) {
                    continue;
                }
                if (a == 0 && b == 0 && c == 0) {
                    continue;
                }
                total = sat_add(total, multinomial(length, a, b), cap_);
                if (total > cap_) {
                    return cap_ + 1U;
                }
            }
        }
        return total;
    }

    u64 pack_state(const int pos, const int u1, const int u2, const int u3) const {
        return (static_cast<u64>(pos) << 48U) | (static_cast<u64>(u1) << 32U) |
               (static_cast<u64>(u2) << 16U) | static_cast<u64>(u3);
    }

    u64 count_with_prefix(const int pos, const int u1, const int u2, const int u3) {
        const u64 key = pack_state(pos, u1, u2, u3);
        const auto it = memo_.find(key);
        if (it != memo_.end()) {
            return it->second;
        }

        const int rem = length_ - pos;
        u64 total = 0;

        for (int A = u1; A <= length_; ++A) {
            if (A > 0 && !is123_[static_cast<std::size_t>(A)]) {
                continue;
            }
            const int max_b = length_ - A;
            if (u2 > max_b) {
                continue;
            }
            for (int B = u2; B <= max_b; ++B) {
                const int C = length_ - A - B;
                if (C < u3) {
                    continue;
                }
                if (B > 0 && !is123_[static_cast<std::size_t>(B)]) {
                    continue;
                }
                if (C > 0 && !is123_[static_cast<std::size_t>(C)]) {
                    continue;
                }

                const int a = A - u1;
                const int b = B - u2;
                const int c = C - u3;
                if (a + b + c != rem) {
                    continue;
                }

                total = sat_add(total, multinomial(rem, a, b), cap_);
                if (total > cap_) {
                    memo_.emplace(key, cap_ + 1U);
                    return cap_ + 1U;
                }
            }
        }

        memo_.emplace(key, total);
        return total;
    }

    const u64 cap_;
    const std::vector<std::uint8_t>& is123_;
    std::vector<std::vector<u64>> choose_;
    int length_ = 0;
    std::unordered_map<u64, u64> memo_;
};

u64 mod_of_decimal_string(const std::string& s, const u64 mod) {
    u64 value = 0;
    for (const char ch : s) {
        value = (value * 10U + static_cast<u64>(ch - '0')) % mod;
    }
    return value;
}

std::string nth_123_number(const u64 n, const std::vector<std::uint8_t>& is123) {
    Nth123Solver solver(n, is123);
    return solver.solve(n);
}

}  // namespace

int main() {
    const std::vector<std::uint8_t> is123 = build_is123(kIs123Limit);

    assert(nth_123_number(4U, is123) == "11");
    assert(nth_123_number(10U, is123) == "31");
    assert(nth_123_number(40U, is123) == "1112");
    assert(nth_123_number(1000U, is123) == "1223321");
    assert(nth_123_number(6000U, is123) == "2333333333323");

    const std::string value = nth_123_number(kTargetN, is123);
    std::cout << mod_of_decimal_string(value, kMod) << '\n';
    return 0;
}

Python

import sys

sys.setrecursionlimit(20000)

def build_is123(limit):
    is123 = [False] * (limit + 1)
    is123[1] = True
    for x in range(2, limit + 1):
        s = str(x)
        c1 = c2 = c3 = 0
        valid = True
        for ch in s:
            if ch == '1': c1 += 1
            elif ch == '2': c2 += 1
            elif ch == '3': c3 += 1
            else:
                valid = False
                break
        if not valid: continue
        if (c1 == 0 or is123[c1]) and (c2 == 0 or is123[c2]) and (c3 == 0 or is123[c3]):
            is123[x] = True
    return is123

class Nth123Solver:
    def __init__(self, cap, is123):
        self.cap = cap
        self.is123 = is123
        self.choose = [[1]]
        self.memo = {}
        self.length = 0
        
    def ensure_choose(self, n):
        while len(self.choose) <= n:
            m = len(self.choose)
            row = [0] * (m + 1)
            row[0] = 1
            row[m] = 1
            for k in range(1, m):
                val = self.choose[m - 1][k - 1] + self.choose[m - 1][k]
                row[k] = min(val, self.cap + 1)
            self.choose.append(row)
            
    def multinomial(self, n, a, b):
        self.ensure_choose(n)
        first = self.choose[n][a]
        second = self.choose[n - a][b]
        return min(first * second, self.cap + 1)

    def count_length(self, length):
        total = 0
        for a in range(length + 1):
            if a > 0 and not self.is123[a]: continue
            for b in range(length - a + 1):
                c = length - a - b
                if b > 0 and not self.is123[b]: continue
                if c > 0 and not self.is123[c]: continue
                if a == 0 and b == 0 and c == 0: continue
                
                total += self.multinomial(length, a, b)
                if total > self.cap:
                    return self.cap + 1
        return total

    def count_with_prefix(self, pos, u1, u2, u3):
        key = (pos, u1, u2, u3)
        if key in self.memo: return self.memo[key]
        
        rem = self.length - pos
        total = 0
        
        for A in range(u1, self.length + 1):
            if A > 0 and not self.is123[A]: continue
            max_b = self.length - A
            if u2 > max_b: continue
            for B in range(u2, max_b + 1):
                C = self.length - A - B
                if C < u3: continue
                if B > 0 and not self.is123[B]: continue
                if C > 0 and not self.is123[C]: continue
                
                a = A - u1
                b = B - u2
                c = C - u3
                if a + b + c != rem: continue
                
                total += self.multinomial(rem, a, b)
                if total > self.cap:
                    self.memo[key] = self.cap + 1
                    return self.cap + 1
                    
        self.memo[key] = total
        return total

    def solve(self, n):
        cumulative = 0
        self.length = 0
        
        while True:
            self.length += 1
            count = self.count_length(self.length)
            if cumulative + count >= n:
                break
            cumulative += count
            
        rank = n - cumulative
        self.memo.clear()
        
        u1 = u2 = u3 = 0
        out = []
        
        for pos in range(self.length):
            for d in range(1, 4):
                n1 = u1 + (1 if d == 1 else 0)
                n2 = u2 + (1 if d == 2 else 0)
                n3 = u3 + (1 if d == 3 else 0)
                
                cnt = self.count_with_prefix(pos + 1, n1, n2, n3)
                if rank > cnt:
                    rank -= cnt
                else:
                    out.append(str(d))
                    u1, u2, u3 = n1, n2, n3
                    break
                    
        return "".join(out)

def solve():
    kTargetN = 111111111111222333
    kMod = 123123123
    kIs123Limit = 5000
    
    is123 = build_is123(kIs123Limit)
    solver = Nth123Solver(kTargetN, is123)
    val_str = solver.solve(kTargetN)
    
    value = 0
    for ch in val_str:
        value = (value * 10 + int(ch)) % kMod
        
    return str(value)

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

Java

import java.util.*;

public class Euler698 {
    static final long kTargetN = 111111111111222333L;
    static final long kMod = 123123123L;
    static final int kIs123Limit = 5000;

    static long satAdd(long a, long b, long cap) {
        long v = a + b;
        if (v < 0 || v > cap)
            return cap + 1;
        return v;
    }

    static long satMul(long a, long b, long cap) {
        if (a == 0 || b == 0)
            return 0;
        if (a > cap / b + 1)
            return cap + 1;
        long v = a * b;
        if (v > cap)
            return cap + 1;
        return v;
    }

    static boolean[] buildIs123(int limit) {
        boolean[] is123 = new boolean[limit + 1];
        is123[1] = true;
        for (int x = 2; x <= limit; ++x) {
            String s = Integer.toString(x);
            int c1 = 0, c2 = 0, c3 = 0;
            boolean valid = true;
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch == '1')
                    c1++;
                else if (ch == '2')
                    c2++;
                else if (ch == '3')
                    c3++;
                else {
                    valid = false;
                    break;
                }
            }
            if (!valid)
                continue;
            if ((c1 == 0 || is123[c1]) && (c2 == 0 || is123[c2]) && (c3 == 0 || is123[c3])) {
                is123[x] = true;
            }
        }
        return is123;
    }

    static class Nth123Solver {
        long cap;
        boolean[] is123;
        List<long[]> choose = new ArrayList<>();
        int length = 0;
        HashMap<Long, Long> memo = new HashMap<>();

        Nth123Solver(long cap, boolean[] is123) {
            this.cap = cap;
            this.is123 = is123;
            choose.add(new long[] { 1L });
        }

        void ensureChoose(int n) {
            while (choose.size() <= n) {
                int m = choose.size();
                long[] row = new long[m + 1];
                row[0] = 1L;
                row[m] = 1L;
                long[] prev = choose.get(m - 1);
                for (int k = 1; k < m; ++k) {
                    row[k] = satAdd(prev[k - 1], prev[k], cap);
                }
                choose.add(row);
            }
        }

        long multinomial(int n, int a, int b) {
            ensureChoose(n);
            long first = choose.get(n)[a];
            long second = choose.get(n - a)[b];
            return satMul(first, second, cap);
        }

        long countLength(int length) {
            long total = 0;
            for (int a = 0; a <= length; ++a) {
                if (a > 0 && !is123[a])
                    continue;
                for (int b = 0; b + a <= length; ++b) {
                    int c = length - a - b;
                    if (b > 0 && !is123[b])
                        continue;
                    if (c > 0 && !is123[c])
                        continue;
                    if (a == 0 && b == 0 && c == 0)
                        continue;
                    total = satAdd(total, multinomial(length, a, b), cap);
                    if (total > cap)
                        return cap + 1;
                }
            }
            return total;
        }

        long packState(int pos, int u1, int u2, int u3) {
            return ((long) pos << 48) | ((long) u1 << 32) | ((long) u2 << 16) | u3;
        }

        long countWithPrefix(int pos, int u1, int u2, int u3) {
            long key = packState(pos, u1, u2, u3);
            if (memo.containsKey(key))
                return memo.get(key);

            int rem = length - pos;
            long total = 0;

            for (int A = u1; A <= length; ++A) {
                if (A > 0 && !is123[A])
                    continue;
                int maxB = length - A;
                if (u2 > maxB)
                    continue;
                for (int B = u2; B <= maxB; ++B) {
                    int C = length - A - B;
                    if (C < u3)
                        continue;
                    if (B > 0 && !is123[B])
                        continue;
                    if (C > 0 && !is123[C])
                        continue;

                    int a = A - u1;
                    int b = B - u2;
                    int c = C - u3;
                    if (a + b + c != rem)
                        continue;

                    total = satAdd(total, multinomial(rem, a, b), cap);
                    if (total > cap) {
                        memo.put(key, cap + 1);
                        return cap + 1;
                    }
                }
            }

            memo.put(key, total);
            return total;
        }

        String solveStr(long n) {
            long cumulative = 0;
            length = 0;

            while (true) {
                length++;
                long count = countLength(length);
                if (satAdd(cumulative, count, cap) >= n) {
                    break;
                }
                cumulative += count;
            }

            long rankInLength = n - cumulative;
            memo.clear();

            int used1 = 0, used2 = 0, used3 = 0;
            StringBuilder out = new StringBuilder(length);

            for (int pos = 0; pos < length; ++pos) {
                for (int d = 1; d <= 3; ++d) {
                    int n1 = used1 + (d == 1 ? 1 : 0);
                    int n2 = used2 + (d == 2 ? 1 : 0);
                    int n3 = used3 + (d == 3 ? 1 : 0);

                    long cnt = countWithPrefix(pos + 1, n1, n2, n3);
                    if (rankInLength > cnt) {
                        rankInLength -= cnt;
                    } else {
                        out.append((char) ('0' + d));
                        used1 = n1;
                        used2 = n2;
                        used3 = n3;
                        break;
                    }
                }
            }
            return out.toString();
        }
    }

    public static String solve() {
        boolean[] is123 = buildIs123(kIs123Limit);
        Nth123Solver solver = new Nth123Solver(kTargetN, is123);
        String valStr = solver.solveStr(kTargetN);

        long value = 0;
        for (int i = 0; i < valStr.length(); ++i) {
            value = (value * 10 + (valStr.charAt(i) - '0')) % kMod;
        }
        return Long.toString(value);
    }

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