Problem 830: Binomials and Powers

View on Project Euler

Project Euler Problem 830 Solution

EulerSolve provides an optimized solution for Project Euler Problem 830, Binomials and Powers, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The quantity of interest is $$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n.$$ For this problem, the target input is \(n=10^{18}\), and the required output is the residue of \(S(10^{18})\) modulo $$M=83^3\cdot 89^3\cdot 97^3.$$ A direct summation is hopeless, so the solution rewrites the sum into a form where only a short range of indices matters modulo each prime cube. Mathematical Approach The key idea is to replace the ordinary power \(k^n\) by a falling-factorial expansion, evaluate the resulting binomial convolution exactly, and then solve the problem separately modulo \(83^3\), \(89^3\), and \(97^3\). Step 1: Expand \(k^n\) in the falling-factorial basis Let $$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$$ denote the falling factorial. The standard Stirling expansion is $$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j,$$ where \(\left\{{n \atop j}\right\}\) is a Stirling number of the second kind. Substituting into the original sum gives $$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j.$$ For \(n>0\), the \(j=0\) term vanishes, so the effective sum starts at \(j=1\)....

Detailed mathematical approach

Problem Summary

The quantity of interest is

$$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n.$$

For this problem, the target input is \(n=10^{18}\), and the required output is the residue of \(S(10^{18})\) modulo

$$M=83^3\cdot 89^3\cdot 97^3.$$

A direct summation is hopeless, so the solution rewrites the sum into a form where only a short range of indices matters modulo each prime cube.

Mathematical Approach

The key idea is to replace the ordinary power \(k^n\) by a falling-factorial expansion, evaluate the resulting binomial convolution exactly, and then solve the problem separately modulo \(83^3\), \(89^3\), and \(97^3\).

Step 1: Expand \(k^n\) in the falling-factorial basis

Let

$$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$$

denote the falling factorial. The standard Stirling expansion is

$$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j,$$

where \(\left\{{n \atop j}\right\}\) is a Stirling number of the second kind. Substituting into the original sum gives

$$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j.$$

For \(n>0\), the \(j=0\) term vanishes, so the effective sum starts at \(j=1\).

Step 2: Collapse the inner binomial sum

Since \((k)_j=j!\binom{k}{j}\), we obtain

$$\sum_{k=0}^{n}\binom{n}{k}(k)_j=j!\sum_{k=j}^{n}\binom{n}{k}\binom{k}{j}.$$

Use the identity

$$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$$

to rewrite the sum as

$$j!\binom{n}{j}\sum_{k=j}^{n}\binom{n-j}{k-j}=j!\binom{n}{j}2^{n-j}.$$

Because \(j!\binom{n}{j}=n^{\underline{j}}\), the whole problem becomes

$$S(n)=\sum_{j=1}^{n}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}.$$

This is the central transformation used by the implementations.

Step 3: Truncate the sum modulo \(p^3\)

Fix one of the primes \(p\in\{83,89,97\}\). We want the transformed sum modulo \(p^3\).

If \(j\ge 3p\), then the falling factorial

$$n^{\underline{j}}=n(n-1)\cdots(n-j+1)$$

contains at least three multiples of \(p\), because any block of \(3p\) consecutive integers contains three such multiples. Therefore

$$v_p\!\left(n^{\underline{j}}\right)\ge 3,$$

so the entire \(j\)-th term is \(0\pmod{p^3}\). Hence

$$S(n)\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$

This short cutoff is what makes the computation feasible.

Step 4: Recover the Stirling term without unsafe division

The finite-difference formula gives

$$j!\left\{{n \atop j}\right\}=\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^n.$$

Call the right-hand side \(D_j\). Directly dividing by \(j!\) modulo \(p^3\) is dangerous when \(p\mid j!\). So write

$$j!=p^{a_j}q_j,\qquad p\nmid q_j.$$

Then \(q_j\) is invertible modulo \(p^3\), and

$$\left\{{n \atop j}\right\}\equiv \frac{D_j}{p^{a_j}}\,q_j^{-1}\pmod{p^3}.$$

To do this safely, we need \(D_j\) modulo \(p^{3+a_j}\). In the active range \(j<3p\), we have \(a_j\le 2\), so a uniform modulus \(p^5\) is enough for every \(j\). That is why the implementation builds the finite-difference numerator modulo \(p^5\), strips the exact power of \(p\), and only then multiplies by the inverse of the unit part \(q_j\) modulo \(p^3\).

Step 5: Solve each prime cube and combine with CRT

For each \(p\in\{83,89,97\}\), compute

$$r_p\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$

The three moduli \(83^3\), \(89^3\), and \(97^3\) are pairwise coprime, so the Chinese Remainder Theorem reconstructs the unique residue \(R\) modulo

$$M=83^3\cdot 89^3\cdot 97^3$$

such that

$$R\equiv r_{83}\pmod{83^3},\qquad R\equiv r_{89}\pmod{89^3},\qquad R\equiv r_{97}\pmod{97^3}.$$

That residue is the required answer.

Worked Example: \(n=3\)

Directly,

$$S(3)=\binom{3}{0}0^3+\binom{3}{1}1^3+\binom{3}{2}2^3+\binom{3}{3}3^3=0+3+24+27=54.$$

Now use the transformed formula. The relevant Stirling numbers are

$$\left\{{3 \atop 1}\right\}=1,\qquad \left\{{3 \atop 2}\right\}=3,\qquad \left\{{3 \atop 3}\right\}=1.$$

Also,

$$3^{\underline{1}}=3,\qquad 3^{\underline{2}}=6,\qquad 3^{\underline{3}}=6.$$

Therefore

$$\begin{aligned} S(3) &=\left\{{3 \atop 1}\right\}3^{\underline{1}}2^2 +\left\{{3 \atop 2}\right\}3^{\underline{2}}2^1 +\left\{{3 \atop 3}\right\}3^{\underline{3}}2^0\\ &=1\cdot 3\cdot 4+3\cdot 6\cdot 2+1\cdot 6\cdot 1\\ &=12+36+6=54. \end{aligned}$$

This confirms the transformation on a small case before the modular machinery is applied to \(n=10^{18}\).

How the Code Works

The implementation handles the three prime cubes \(83^3\), \(89^3\), and \(97^3\) separately. For one prime \(p\), it sets \(J=\min(n,3p-1)\), because terms beyond that point are already zero modulo \(p^3\).

Next it builds a Pascal-style table of \(\binom{j}{i}\) for \(0\le i\le j\le J\) modulo \(p^5\), and it precomputes \(i^n\bmod p^5\) for every \(0\le i\le J\). It also tabulates, for each \(j\), the \(p\)-adic valuation of \(j!\) and the remaining unit factor of \(j!\) modulo \(p^3\).

During the main loop, the implementation updates \(n^{\underline{j}}\) multiplicatively by appending the next factor \(n-j+1\), and it updates \(2^{n-j}\) by multiplying once per step by the inverse of \(2\) modulo \(p^3\). It then evaluates the finite-difference numerator \(D_j\), removes the exact power of \(p\) contributed by \(j!\), multiplies by the inverse of the unit part of \(j!\), and accumulates the resulting term modulo \(p^3\).

After obtaining the three residues, the implementation combines them with the Chinese Remainder Theorem. The C++ implementation evaluates the three prime channels in parallel, while the Python and Java implementations process them sequentially. The C++ implementation also performs a small validation at \(n=10\), where \(S(10)=142469423360\), and checks that the modular pipeline reproduces the same residue modulo \(M\).

Complexity Analysis

For one prime \(p\), let \(J=\min(n,3p-1)\). Building the binomial table up to row \(J\) costs \(O(J^2)\) time and \(O(J^2)\) memory. Precomputing the powers \(i^n\bmod p^5\) for \(0\le i\le J\) costs \(O(J\log n)\) time.

The main summation also costs \(O(J^2)\) time, because the finite-difference formula for the \(j\)-th Stirling term sums over all \(i=0,\dots,j\). Thus one prime channel costs

$$O(J^2+J\log n)$$

time and \(O(J^2)\) memory. Since the actual primes are fixed and \(J<3p\), the total workload across \(83\), \(89\), and \(97\) is effectively constant for the target input \(n=10^{18}\).

Footnotes and References

  1. Project Euler problem page: https://projecteuler.net/problem=830
  2. Stirling numbers of the second kind: Wikipedia — Stirling numbers of the second kind
  3. Falling factorials: Wikipedia — Falling and rising factorials
  4. Finite differences: Wikipedia — Finite difference
  5. Legendre's formula for \(v_p(n!)\): Wikipedia — Legendre's formula
  6. Chinese remainder theorem: Wikipedia — Chinese remainder theorem

Problem 830 source code

C++

#include <cstdint>
#include <iostream>
#include <thread>
#include <vector>

using namespace std;

namespace {

using int64 = long long;
using i128 = __int128_t;

int64 pow_int(int64 base, int exp) {
    int64 res = 1;
    for (int i = 0; i < exp; ++i) res *= base;
    return res;
}

int64 mod_pow(int64 base, long long exp, int64 mod) {
    int64 res = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = static_cast<i128>(res) * base % mod;
        base = static_cast<i128>(base) * base % mod;
        exp >>= 1;
    }
    return res;
}

int64 ext_gcd(int64 a, int64 b, int64 &x, int64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int64 x1 = 0, y1 = 0;
    int64 g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return g;
}

int64 mod_inv(int64 a, int64 mod) {
    int64 x = 0, y = 0;
    int64 g = ext_gcd(a, mod, x, y);
    if (g != 1) return 0;
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

int64 compute_mod_prime(long long n, int p) {
    int64 mod_p3 = pow_int(p, 3);
    if (n == 0) return 1 % mod_p3;

    int max_j = static_cast<int>(min<long long>(n, 3LL * p - 1));
    int64 mod_big = pow_int(p, 5); // p^{3+2} is enough since max_j < 3p.

    vector<vector<int64>> binom(max_j + 1, vector<int64>(max_j + 1, 0));
    binom[0][0] = 1;
    for (int j = 1; j <= max_j; ++j) {
        binom[j][0] = 1;
        binom[j][j] = 1;
        for (int i = 1; i < j; ++i) {
            int64 v = binom[j - 1][i - 1] + binom[j - 1][i];
            if (v >= mod_big) v -= mod_big;
            binom[j][i] = v;
        }
    }

    vector<int64> pow_i(max_j + 1, 0);
    for (int i = 0; i <= max_j; ++i) {
        pow_i[i] = mod_pow(i, n, mod_big);
    }

    vector<int> vp_fact(max_j + 1, 0);
    vector<int64> u_fact(max_j + 1, 0);
    u_fact[0] = 1 % mod_p3;
    for (int j = 1; j <= max_j; ++j) {
        int temp = j;
        int cnt = 0;
        while (temp % p == 0) {
            temp /= p;
            ++cnt;
        }
        vp_fact[j] = vp_fact[j - 1] + cnt;
        u_fact[j] = static_cast<i128>(u_fact[j - 1]) * (temp % mod_p3) % mod_p3;
    }

    int64 inv2 = mod_inv(2 % mod_p3, mod_p3);
    int64 pow2 = mod_pow(2, n, mod_p3);
    int64 n_mod = n % mod_p3;
    int64 fall = 1 % mod_p3;
    int64 sum = 0;

    for (int j = 1; j <= max_j; ++j) {
        int64 factor = n_mod - (j - 1);
        factor %= mod_p3;
        if (factor < 0) factor += mod_p3;
        fall = static_cast<i128>(fall) * factor % mod_p3;
        pow2 = static_cast<i128>(pow2) * inv2 % mod_p3; // now 2^{n-j}

        int a = vp_fact[j];
        int64 mod_ext = mod_p3;
        for (int t = 0; t < a; ++t) mod_ext *= p;

        int64 N = 0;
        for (int i = 0; i <= j; ++i) {
            int64 term = static_cast<i128>(binom[j][i]) * pow_i[i] % mod_big;
            if ((j - i) & 1) {
                N -= term;
                if (N < 0) N += mod_big;
            } else {
                N += term;
                if (N >= mod_big) N -= mod_big;
            }
        }
        if (mod_ext != mod_big) N %= mod_ext;
        if (N < 0) N += mod_ext;
        int64 N_div = N;
        for (int t = 0; t < a; ++t) N_div /= p;

        int64 inv_u = mod_inv(u_fact[j], mod_p3);
        int64 stirling = static_cast<i128>(N_div % mod_p3) * inv_u % mod_p3;

        int64 term = static_cast<i128>(stirling) * fall % mod_p3;
        term = static_cast<i128>(term) * pow2 % mod_p3;
        sum += term;
        sum %= mod_p3;
    }

    return sum % mod_p3;
}

unsigned long long compute_naive(unsigned int n) {
    unsigned __int128 sum = 0;
    unsigned __int128 binom = 1;
    for (unsigned int k = 0; k <= n; ++k) {
        if (k > 0) {
            binom = binom * (n - k + 1) / k;
        }
        unsigned __int128 powk = 1;
        for (unsigned int i = 0; i < n; ++i) powk *= k;
        sum += binom * powk;
    }
    return static_cast<unsigned long long>(sum);
}

int64 combine_crt(const vector<int64> &rem, const vector<int64> &mods) {
    int64 M = 1;
    for (int64 m : mods) M *= m;
    int64 result = 0;
    for (size_t i = 0; i < mods.size(); ++i) {
        int64 Mi = M / mods[i];
        int64 inv = mod_inv(Mi % mods[i], mods[i]);
        int64 term = static_cast<i128>(rem[i]) * Mi % M;
        term = static_cast<i128>(term) * inv % M;
        result += term;
        result %= M;
    }
    return result;
}

int64 compute_mod_all(long long n) {
    vector<int> primes = {83, 89, 97};
    vector<int64> mods(3, 0);
    vector<int64> rems(3, 0);

    vector<thread> threads;
    threads.reserve(primes.size());
    for (size_t i = 0; i < primes.size(); ++i) {
        threads.emplace_back([&, i]() {
            int p = primes[i];
            mods[i] = pow_int(p, 3);
            rems[i] = compute_mod_prime(n, p);
        });
    }
    for (auto &t : threads) t.join();

    return combine_crt(rems, mods);
}

} // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const unsigned long long s10 = compute_naive(10);
    if (s10 != 142469423360ULL) {
        cerr << "Validation failed: S(10) != 142469423360\n";
        return 1;
    }

    int64 mod_all = pow_int(83, 3) * pow_int(89, 3) * pow_int(97, 3);
    int64 s10_mod = static_cast<int64>(s10 % mod_all);
    int64 s10_fast = compute_mod_all(10);
    if (s10_fast != s10_mod) {
        cerr << "Validation failed: S(10) mod M mismatch\n";
        return 1;
    }

    long long n = 1'000'000'000'000'000'000LL;
    int64 ans = compute_mod_all(n);
    cout << ans << "\n";
    return 0;
}

Python

def pow_int(base, exp):
    return base ** exp

def mod_pow(base, exp, mod):
    return pow(base, exp, mod)

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - y1 * (a // b)
    return g, x, y

def mod_inv(a, mod):
    g, x, y = ext_gcd(a, mod)
    if g != 1: return 0
    return x % mod

def compute_mod_prime(n, p):
    mod_p3 = pow_int(p, 3)
    if n == 0: return 1 % mod_p3
    
    max_j = min(n, 3 * p - 1)
    mod_big = pow_int(p, 5)
    
    binom = [[0] * (max_j + 1) for _ in range(max_j + 1)]
    binom[0][0] = 1
    for j in range(1, max_j + 1):
        binom[j][0] = 1
        binom[j][j] = 1
        for i in range(1, j):
            v = binom[j - 1][i - 1] + binom[j - 1][i]
            if v >= mod_big: v -= mod_big
            binom[j][i] = v
            
    pow_i = [mod_pow(i, n, mod_big) for i in range(max_j + 1)]
    
    vp_fact = [0] * (max_j + 1)
    u_fact = [0] * (max_j + 1)
    u_fact[0] = 1 % mod_p3
    
    for j in range(1, max_j + 1):
        temp = j
        cnt = 0
        while temp % p == 0:
            temp //= p
            cnt += 1
        vp_fact[j] = vp_fact[j - 1] + cnt
        u_fact[j] = (u_fact[j - 1] * (temp % mod_p3)) % mod_p3
        
    inv2 = mod_inv(2 % mod_p3, mod_p3)
    pow2 = mod_pow(2, n, mod_p3)
    n_mod = n % mod_p3
    fall = 1 % mod_p3
    total_sum = 0
    
    for j in range(1, max_j + 1):
        factor = (n_mod - (j - 1)) % mod_p3
        if factor < 0: factor += mod_p3
        fall = (fall * factor) % mod_p3
        pow2 = (pow2 * inv2) % mod_p3
        
        a = vp_fact[j]
        mod_ext = mod_p3 * pow_int(p, a)
        
        N = 0
        for i in range(j + 1):
            term = (binom[j][i] * pow_i[i]) % mod_big
            if (j - i) & 1:
                N -= term
                if N < 0: N += mod_big
            else:
                N += term
                if N >= mod_big: N -= mod_big
                
        if mod_ext != mod_big: N %= mod_ext
        if N < 0: N += mod_ext
        
        N_div = N // pow_int(p, a)
        
        inv_u = mod_inv(u_fact[j], mod_p3)
        stirling = ((N_div % mod_p3) * inv_u) % mod_p3
        
        term = (stirling * fall) % mod_p3
        term = (term * pow2) % mod_p3
        total_sum = (total_sum + term) % mod_p3
        
    return total_sum

def combine_crt(rem, mods):
    M = 1
    for m in mods: M *= m
    res = 0
    for i in range(len(mods)):
        Mi = M // mods[i]
        inv = mod_inv(Mi % mods[i], mods[i])
        term = (rem[i] * Mi) % M
        term = (term * inv) % M
        res = (res + term) % M
    return res

def compute_mod_all(n):
    primes = [83, 89, 97]
    mods = [pow_int(p, 3) for p in primes]
    rems = [compute_mod_prime(n, p) for p in primes]
    return combine_crt(rems, mods)

def solve():
    n = 1000000000000000000
    ans = compute_mod_all(n)
    return str(ans)

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

Java

public class Euler830 {

    static long powInt(long base, int exp) {
        long res = 1;
        for (int i = 0; i < exp; ++i)
            res *= base;
        return res;
    }

    static long mulMod(long a, long b, long mod) {
        long q = (long) ((double) a * b / mod);
        long r = a * b - q * mod;
        while (r < 0)
            r += mod;
        while (r >= mod)
            r -= mod;
        return r;
    }

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

    static class GCDResult {
        long g;
        long x;
        long y;

        GCDResult(long g, long x, long y) {
            this.g = g;
            this.x = x;
            this.y = y;
        }
    }

    static GCDResult extGcd(long a, long b) {
        if (b == 0) {
            return new GCDResult(a, 1, 0);
        }
        GCDResult res = extGcd(b, a % b);
        long x = res.y;
        long y = res.x - res.y * (a / b);
        return new GCDResult(res.g, x, y);
    }

    static long modInv(long a, long mod) {
        GCDResult res = extGcd(a, mod);
        if (res.g != 1)
            return 0;
        long x = res.x % mod;
        if (x < 0)
            x += mod;
        return x;
    }

    static long computeModPrime(long n, int p) {
        long modP3 = powInt(p, 3);
        if (n == 0)
            return 1 % modP3;

        int maxJ = (int) Math.min(n, 3L * p - 1);
        long modBig = powInt(p, 5);

        long[][] binom = new long[maxJ + 1][maxJ + 1];
        binom[0][0] = 1;
        for (int j = 1; j <= maxJ; ++j) {
            binom[j][0] = 1;
            binom[j][j] = 1;
            for (int i = 1; i < j; ++i) {
                long v = binom[j - 1][i - 1] + binom[j - 1][i];
                if (v >= modBig)
                    v -= modBig;
                binom[j][i] = v;
            }
        }

        long[] powI = new long[maxJ + 1];
        for (int i = 0; i <= maxJ; ++i) {
            powI[i] = modPow(i, n, modBig);
        }

        int[] vpFact = new int[maxJ + 1];
        long[] uFact = new long[maxJ + 1];
        uFact[0] = 1 % modP3;

        for (int j = 1; j <= maxJ; ++j) {
            int temp = j;
            int cnt = 0;
            while (temp % p == 0) {
                temp /= p;
                cnt++;
            }
            vpFact[j] = vpFact[j - 1] + cnt;
            uFact[j] = mulMod(uFact[j - 1], temp % modP3, modP3);
        }

        long inv2 = modInv(2 % modP3, modP3);
        long pow2 = modPow(2, n, modP3);
        long nMod = n % modP3;
        long fall = 1 % modP3;
        long sum = 0;

        for (int j = 1; j <= maxJ; ++j) {
            long factor = (nMod - (j - 1)) % modP3;
            if (factor < 0)
                factor += modP3;
            fall = mulMod(fall, factor, modP3);
            pow2 = mulMod(pow2, inv2, modP3);

            int a = vpFact[j];
            long modExt = modP3;
            for (int t = 0; t < a; ++t)
                modExt *= p;

            long N = 0;
            for (int i = 0; i <= j; ++i) {
                long term = mulMod(binom[j][i], powI[i], modBig);
                if ((j - i) % 2 != 0) {
                    N -= term;
                    if (N < 0)
                        N += modBig;
                } else {
                    N += term;
                    if (N >= modBig)
                        N -= modBig;
                }
            }
            if (modExt != modBig)
                N %= modExt;
            if (N < 0)
                N += modExt;

            long NDiv = N;
            for (int t = 0; t < a; ++t)
                NDiv /= p;

            long invU = modInv(uFact[j], modP3);
            long stirling = mulMod(NDiv % modP3, invU, modP3);

            long term = mulMod(stirling, fall, modP3);
            term = mulMod(term, pow2, modP3);
            sum = (sum + term) % modP3;
        }

        return sum % modP3;
    }

    static long combineCrt(long[] rem, long[] mods) {
        long M = 1;
        for (long m : mods)
            M *= m;
        long result = 0;
        for (int i = 0; i < mods.length; ++i) {
            long Mi = M / mods[i];
            long inv = modInv(Mi % mods[i], mods[i]);
            long term = mulMod(rem[i], Mi, M);
            term = mulMod(term, inv, M);
            result = (result + term) % M;
        }
        return result;
    }

    static long computeModAll(long n) {
        int[] primes = { 83, 89, 97 };
        long[] mods = new long[3];
        long[] rems = new long[3];

        for (int i = 0; i < 3; ++i) {
            mods[i] = powInt(primes[i], 3);
            rems[i] = computeModPrime(n, primes[i]);
        }

        return combineCrt(rems, mods);
    }

    public static String solve() {
        long n = 1000000000000000000L;
        long ans = computeModAll(n);
        return Long.toString(ans);
    }

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