Problem 148: Exploring Pascal's Triangle

Project Euler Problem 148 Solution

EulerSolve provides an optimized solution for Project Euler Problem 148, Exploring Pascal's Triangle, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For the first $10^9$ rows of Pascal's triangle, count how many binomial coefficients are not divisible by 7. If row $n$ is written as $\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}$, then a brute-force approach would have to inspect an enormous number of entries, so the only viable route is to exploit the arithmetic structure of binomial coefficients modulo 7. Let $r(n)$ denote the number of entries in row $n$ that are not divisible by 7, and let $F(N)=\sum_{n=0}^{N-1} r(n)$. The required answer is $F(10^9)$. Mathematical Approach Lucas' theorem turns one row into a digit product Write $n$ and $k$ in base 7 as $$n=\sum_i d_i 7^i,\qquad k=\sum_i e_i 7^i.$$ Lucas' theorem states that for a prime $p$, $$\binom{n}{k}\equiv \prod_i \binom{d_i}{e_i}\pmod p.$$ With $p=7$, the product is nonzero modulo 7 exactly when every digit satisfies $e_i\le d_i$. For one fixed digit $d_i$, there are $d_i+1$ allowed choices for $e_i$. Therefore the number of entries in row $n$ that survive modulo 7 is $$r(n)=\prod_i (d_i+1).$$ This is the central object of the problem: each row is reduced to a simple product of its base-7 digits plus one. Why complete blocks of $7^m$ rows collapse to $28^m$ Consider all rows with $0\le n<7^m$....

Detailed mathematical approach

Problem Summary

We must count the entries that are not divisible by $7$ in the first $10^9$ rows of Pascal's triangle. ^[1] The triangle starts with a single $1$; every later row starts and ends with $1$, and every other entry is the sum of the two entries above it. With rows and positions numbered from $0$, row $n$ consists of the $n+1$ binomial coefficients $\binom n0,\binom n1,\dots,\binom nn$. ^[2] The statement shows that none of the $28$ entries of the first seven rows, rows $0$ to $6$, is divisible by $7$, and that only $2361$ of the $5050$ entries of the first one hundred rows are not divisible by $7$; since $5050=100\cdot101/2$, these are the rows $0$ to $99$, and the first $10^9$ rows are the rows $0$ to $10^9-1$. We write $r(n)$ for the number of such entries in row $n$ and $F(N)=r(0)+r(1)+\dots+r(N-1)$ for their number in the first $N$ rows, so $F(7)=28$ and $F(100)=2361$, and we want $F(10^9)$.

The whole solution in one sentence: by Lucas's theorem an entry $\binom nk$ is not divisible by $7$ exactly when no base-$7$ digit of $k$ is larger than the matching digit of $n$, so row $n$ has $\prod(n_i+1)$ such entries, and since the first $7^m$ rows contain exactly $28^m$ of them, the total for the first $10^9$ rows follows from one short pass over the $11$ base-$7$ digits of $10^9$ that counts whole blocks of rows at once.

Mathematical Approach

We look at small rows, prove their pattern with Lucas's theorem, and then add up the rows block by block.

1. Small rows modulo 7

Only divisibility by $7$ matters, so we may replace every entry by its remainder modulo $7$. Remainders can be added like the numbers themselves: if $a\equiv a'$ and $b\equiv b'\pmod 7$, then $a+b\equiv a'+b'\pmod 7$, and the same holds for products. ^[3] So the triangle of remainders is built by the same rule, and an entry is divisible by $7$ exactly when its remainder is $0$. Row $7$ is $1,7,21,35,35,21,7,1$, with the remainders $1,0,0,0,0,0,0,1$: only the two ends survive. The next rows of remainders are

row $8$: $1,1,0,0,0,0,0,1,1$, with $4$ nonzero entries;
row $9$: $1,2,1,0,0,0,0,1,2,1$, with $6$ nonzero entries.

Row $9$ is row $2$, that is $1,2,1$, written twice with four zeros between the copies. The counts $r(0),\dots,r(20)$ are $1,2,\dots,7$, then $2,4,\dots,14$, then $3,6,\dots,21$: rows $7$ to $13$ consist of two copies of rows $0$ to $6$, and rows $14$ to $20$ of three, the middle one doubled: row $15$ is $1,1$, five zeros, $2,2$, five zeros, $1,1$.

Base $7$ explains this. Every $n\ge0$ can be written as $n=\sum_in_i7^i$ with digits $0\le n_i\le6$, and in only one way apart from leading zeros: the last digit is the remainder of $n$ on division by $7$, and the other digits are those of the quotient. For example $9=(12)_7$, $15=(21)_7$ and $100=2\cdot49+0\cdot7+2=(202)_7$. Now $r(9)=6=(1+1)(2+1)$ and $r(15)=6=(2+1)(1+1)$: the count looks like the product of the digits, each increased by $1$, which the next sections prove.

2. Lucas's theorem

Write $n$ and $k$ in base $7$ with the same number of digits, padding with leading zeros. Lucas's theorem, published by Édouard Lucas in 1878, states for the prime $7$ that ^[4]

$$\binom nk\equiv\prod_i\binom{n_i}{k_i}\pmod 7,$$

with the convention $\binom ab=0$ for $b\gt a$. Three checks: $10=(13)_7$ and $3=(03)_7$ give $\binom10\binom33=1$, and indeed $\binom{10}3=120=17\cdot7+1$. Next, $5=(05)_7$ brings the factor $\binom35=0$, and indeed $\binom{10}5=252=36\cdot7$. Finally $100=(202)_7$ and $50=(101)_7$ give $\binom21\binom00\binom21=4$, and $\binom{100}{50}$, a number with $30$ digits, indeed leaves the remainder $4$.

3. Why Lucas's theorem holds

Pascal's triangle hides in the powers of $1+x$: $(1+x)^2=1+2x+x^2$ has the coefficients of row $2$, and multiplying by $1+x$ replaces the coefficient of $x^k$ by the sum of the old coefficients of $x^k$ and $x^{k-1}$, which is Pascal's rule. By induction from $(1+x)^0=1$, the coefficient of $x^k$ in $(1+x)^n$ is $\binom nk$, the binomial theorem for $1+x$.

The proof, in the form given by Nathan Fine in 1947, compares polynomials whose coefficients are taken modulo $7$; two such polynomials are congruent when all their coefficients are. ^[4] Multiplying polynomials only adds and multiplies coefficients, so congruent polynomials have congruent products and powers. ^[3]

Step 1. For $1\le j\le6$, the number $\binom7j=7!/(j!\,(7-j)!)$ is divisible by $7$: the factor $7$ of the numerator cannot cancel, because the denominator is a product of numbers from $1$ to $6$, and a prime that divides a product divides one of its factors (Euclid's lemma). ^[5] By the binomial theorem, therefore,

$$(1+x)^7\equiv1+x^7\pmod 7,$$

the "freshman's dream" of algebra. ^[6] Raising both sides to the $7$th power and then using the same identity with $x^7$ in place of $x$ gives $(1+x)^{49}\equiv(1+x^7)^7\equiv1+x^{49}$; repeating this gives $(1+x)^{7^i}\equiv1+x^{7^i}$ for every $i\ge0$.

Step 2. Splitting the exponent $n=\sum_in_i7^i$ gives

$$\begin{aligned}&(1+x)^n=\prod_i\bigl((1+x)^{7^i}\bigr)^{n_i}\\&\quad\equiv\prod_i\bigl(1+x^{7^i}\bigr)^{n_i}\pmod 7,\end{aligned}$$

and by the binomial theorem the $i$-th factor on the right is $\sum_{k_i=0}^{n_i}\binom{n_i}{k_i}x^{k_i7^i}$.

Step 3. Multiplying out, each term comes from a choice of one $k_i$ in each factor and has the exponent $\sum_ik_i7^i$, a base-$7$ representation with the digits $k_i\le n_i\le6$. By its uniqueness, $x^k$ arises only from the digits of $k$ themselves, and only if $k_i\le n_i$ for every $i$. On the left the coefficient of $x^k$ is $\binom nk$, so comparing coefficients gives Lucas's theorem; the product is $0$ as soon as some $k_i\gt n_i$. $\square$

For $n=9=(12)_7$ the proof reads $(1+x)^9\equiv(1+x^7)(1+x)^2$${}=1+2x+x^2+x^7+2x^8+x^9$, exactly row $9$ of Section 1. For two-digit numbers it explains the copies: if $n=7s+t$ and $k=7u+v$ with digits $s,t,u,v$, then $\binom nk\equiv\binom su\binom tv$. So the first $49$ rows consist of copies of the triangle of rows $0$ to $6$, one for each pair $0\le u\le s\le6$, multiplied by $\binom su$, which is not divisible by $7$, with triangles of zeros in between.

4. Counting one row

Claim. Row $n$ contains exactly $r(n)=\prod_i(n_i+1)$ entries that are not divisible by $7$.

Proof. Take $0\le k\le n$; then $k$ has no more digits than $n$. If some digit $k_i\gt n_i$, Lucas's theorem gives $\binom nk\equiv0$. If $k_i\le n_i$ for every $i$, each factor $\binom{n_i}{k_i}$ divides $n_i!$, because $\binom{n_i}{k_i}\,k_i!\,(n_i-k_i)!=n_i!$, and $n_i!$ is a product of numbers below $7$; by Euclid's lemma no factor is divisible by $7$, and neither is their product. Hence $7\nmid\binom nk$ exactly when $k_i\le n_i$ for every $i$. Every choice of digits $0\le k_i\le n_i$ gives a number $k\le n$, and different choices give different numbers, so there are $\prod_i(n_i+1)$ such $k$. $\square$

For row $100=(202)_7$ the claim gives $3\cdot1\cdot3=9$ entries, at the positions whose digits are at most $2,0,2$: $k=0,1,2,49,50,51,98,99,100$, as a direct computation confirms. These row counts form OEIS A382720, whose programs compute them as this product. ^[8] Both uses of Euclid's lemma need a prime: row $4=(10)_4$, that is $1,4,6,4,1$, has three entries not divisible by $4$, not $(1+1)(0+1)=2$.

Kummer's theorem gives a second route: the exponent of $7$ in $\binom nk$ is the number of carries when $k$ and $n-k$ are added in base $7$, ^[7] and there is no carry exactly when the digits of $k$ and $n-k$ add up to those of $n$, that is, when every $k_i\le n_i$.

5. Complete blocks of rows

The rows $0$ to $7^m-1$ are exactly the numbers with $m$ base-$7$ digits, leading zeros allowed, each digit chosen freely from $0$ to $6$. Multiplying out a product of $m$ sums gives one term for every choice of the $m$ digits, so

$$\begin{aligned}F(7^m)&=\sum_{n_{m-1}=0}^{6}\cdots\sum_{n_0=0}^{6}\ \prod_{i=0}^{m-1}(n_i+1)\\&=\Bigl(\sum_{d=0}^{6}(d+1)\Bigr)^m=28^m.\end{aligned}$$

Here $28=1+2+\dots+7$. The case $m=1$ is the statement's $F(7)=28$; for $m=2$, the first $49$ rows hold $784$ such entries out of $1225$, the $28$ copies of Section 3 with $28$ entries each.

6. Cutting at the leading digit

Now let $N\ge1$ have the leading base-$7$ digit $a$ in position $m$, so that $N=a\cdot7^m+b$ with $1\le a\le6$ and $0\le b\lt7^m$. A row $n\lt N$ belongs to one of two groups.

Its digit in position $m$ is some $x\lt a$: then $n=x\cdot7^m+c$ with $0\le c\lt7^m$ free. The digit $x$ contributes the factor $x+1$, and the lower digits contribute $28^m$ in total by Section 5.
Its digit in position $m$ equals $a$: then $n=a\cdot7^m+c$ with $0\le c\lt b$, and $r(n)=(a+1)\,r(c)$.

Adding both groups, with $T(a)=1+2+\dots+a=a(a+1)/2$ and $F(0)=0$,

$$F(N)=T(a)\cdot28^m+(a+1)\,F(b).$$

For $N=100=(202)_7$ we have $m=2$, $a=2$ and $b=2$. The rows $0$ to $48$ contribute $784$, the rows $49$ to $97$, with leading digit $1$, contribute $2\cdot784=1568$, and the rows $98=(200)_7$ and $99=(201)_7$ contribute $3\cdot F(2)=3\cdot(1+2)=9$:

$$F(100)=3\cdot784+3\cdot3=2361,$$

the statement's value.

7. One formula for all digits

Applying the cut again to $b$, and so on, removes at least one digit per step. The result can also be seen directly. Write $N=(a_{L-1}\cdots a_1a_0)_7$ and a row $n\lt N$ with $L$ digits as well, and look at the highest position $i$ in which $n$ and $N$ differ; there the digit $x$ of $n$ is smaller than $a_i$, because $n\lt N$. Above position $i$, $n$ has the digits of $N$, which contribute $P_i=\prod_{j\gt i}(a_j+1)$; position $i$ contributes $x+1$; and the $i$ lower digits are free and contribute $28^i$. Summing over $x\lt a_i$ gives

$$F(N)=\sum_{i=0}^{L-1}P_i\,T(a_i)\,28^i,$$

where the empty product $P_{L-1}$ is $1$. For $N=1000=(2626)_7$ the four positions, from the top, give

$i=3$, digit $2$: $1\cdot3\cdot21952=65856$;
$i=2$, digit $6$: $3\cdot21\cdot784=49392$;
$i=1$, digit $2$: $21\cdot3\cdot28=1764$;
$i=0$, digit $6$: $63\cdot21\cdot1=1323$,

so $F(1000)=118335$, which a direct count over the $500500$ entries of the first $1000$ rows confirms. A digit $0$ adds nothing, since $T(0)=0$, and its factor $0+1=1$ leaves the products below it unchanged, as in position $1$ of $100=(202)_7$.

How the Code Works

The C++ program ^[9] starts in main with rows $=10^9$ and the checkpoints switched on. parse_arguments accepts --skip-checkpoints and --rows= followed by decimal digits, read by parse_u64_after_prefix into an unsigned 64-bit integer; any other argument ends the program with an error message and exit code $1$. run_checkpoints compares the results for $100$ and $7$ rows with the strings "2361" and "28" and returns false if one differs, in which case main ends with exit code $2$; otherwise main prints the count for rows.

count_not_divisible_by_seven returns $0$ for zero rows. Otherwise it collects the base-$7$ digits of rows with % 7 and / 7, lowest first, and reverses the vector, so that digits[0] is the leading digit. The vector pow28 holds $28^0,\dots,28^L$, the block counts of Section 5. The main loop visits the digits from the top. For the digit $d$ at index i, the variable rem $=L-1-i$ is its position, and prefix_product is the product $P_{\mathrm{rem}}$ of Section 7. For each smaller digit $x=0,\dots,d-1$, the inner loop over xdigit adds prefix_product${}\cdot(x+1)\cdot28^{\mathrm{rem}}$, the count for the rows whose first difference from rows is the digit $x$ here, so the loop adds $T(d)$ term by term. Afterwards prefix_product is multiplied by $d+1$, ready for the next position.

All sums are kept in unsigned __int128, a 128-bit integer type that GCC and Clang provide as an extension, ^[10] and to_string_u128 writes the result in decimal by repeated division by $10$. The width is generous: $F(N)$ never exceeds the number $N(N+1)/2$ of entries, about $5\cdot10^{17}$ for $N=10^9$, below the signed 64-bit limit $2^{63}-1\approx9.2\cdot10^{18}$; for every 64-bit row count, $F(N)\lt2^{127}$. The parser has no overflow check: a row count above $2^{64}-1$ wraps around, so --rows=18446744073709551616 is read as $0$ and prints $0$.

The Python program does the same work in solve, which it calls at the end, and the Java program in main; both fix the number of rows at $10^9$, read no arguments and run no checkpoints. Python's integers have unlimited precision; Java computes the digits with long variables, keeps them in a List<Integer> reversed with Collections.reverse, and holds pow28, answer and the prefix product pp as BigInteger values. ^[11] A comment in the Python program states that a digit $d$ contributes $d\cdot28^{\mathrm{rem}}$ times the prefix product; the loop itself correctly adds $T(d)\cdot28^{\mathrm{rem}}$ times it, as in Section 7.

Complexity and Verification

For $N\ge1$ rows the outer loop makes $L=\lfloor\log_7N\rfloor+1$ passes and the inner loop $a_0+a_1+\dots+a_{L-1}\le6L$ steps; with the digit conversion and pow28, and counting each arithmetic operation as one step, the time is $O(\log N)$, and the two vectors hold $O(\log N)$ numbers. For $10^9=(33531600616)_7$ this means $11$ passes, $34$ inner steps and $11$ multiplications for pow28; in tests on a desktop computer each program finished in a few hundredths of a second. A direct simulation of the triangle modulo $7$ would touch all of the roughly $5\cdot10^{17}$ entries, about $16$ years at one entry per nanosecond.

Unless --skip-checkpoints is given, the C++ program checks $F(100)=2361$ and $F(7)=28$ before the main run; the Python and Java programs have no built-in checks. The other checks were made for this article only. Building the first $7^5=16807$ rows modulo $7$, $141246028$ entries, confirms $r(n)=\prod_i(n_i+1)$ for each of these rows; the C++ program with --rows=N, and copies of the Python and Java loops with the row count as a parameter, agree with it for every $N$ from $1$ to $16807$, including $F(16807)=28^5=17210368$. All three programs print the same number for $10^9$ rows, and so does an independent program that adds $r(n)$ row by row over all $10^9$ rows, with the base-$7$ digits of $n$ kept in a counter, which confirms Sections 5 to 7 at full size. For $2^{64}-1$ rows the C++ program agrees with an exact evaluation of Section 6 in Python, and it runs cleanly under checks for undefined behaviour.

Footnotes and References

The references below supply the background facts used above; the block count $28^m$, the cut at the leading digit, the formula of Section 7 and the operation counts are derived in this article.

Project Euler 148 — Exploring Pascal's Triangle. The official statement shows that no entry of the first seven rows is divisible by 7, notes that only 2361 of the 5050 entries of the first one hundred rows are not, and asks for the number of entries not divisible by 7 in the first one billion (10⁹) rows.
Wikipedia — Pascal's triangle. Rows are numbered from n = 0 and the entries of each row from k = 0, and each entry is the sum of the two above it (Pascal's rule).
Wikipedia — Modular arithmetic. Integers are congruent modulo m when their difference is a multiple of m; congruences can be added, multiplied and raised to powers term by term.
Wikipedia — Lucas's theorem. For a prime p, C(m, n) is congruent modulo p to the product of the binomial coefficients of the base-p digits, with C(m, n) = 0 for m < n; so p divides C(m, n) exactly when some base-p digit of n exceeds the corresponding digit of m. The theorem appeared in 1878 in papers by Édouard Lucas; the generating-function proof through (1 + X)ᵖ ≡ 1 + Xᵖ (mod p) is credited to Nathan Fine (1947).
Wikipedia — Euclid's lemma. If a prime p divides a product ab of integers, then p divides a or b; applied repeatedly, a prime dividing none of several factors does not divide their product.
Wikipedia — Freshman's dream. In a commutative ring of prime characteristic p, (x + y)ᵖ = xᵖ + yᵖ, because p divides C(p, k) for 0 < k < p; the identity can be iterated for powers of p.
Wikipedia — Kummer's theorem. For integers n ≥ m ≥ 0 and a prime p, the exponent of p in C(n, m) equals the number of carries when m is added to n − m in base p; Ernst Kummer proved it in 1852.
OEIS A382720 — Number of entries in the n-th row of Pascal's triangle not divisible by 7. It begins 1, 2, 3, 4, 5, 6, 7, 2, 4, 6, …, and its programs compute a(n) as the product of d + 1 over the base-7 digits d of n; its partial sums, the counts for rows 0 to n, are A382726.
C++ — Euler148.cpp. The linked immutable revision, with count_not_divisible_by_seven and run_checkpoints, is the implementation record for this article.
GCC manual — 128-bit Integers. GCC supports the type __int128, and unsigned __int128 for unsigned values, on targets with an integer mode wide enough to hold 128 bits.
Python — numeric types states that integers have unlimited precision, and Java — BigInteger describes immutable arbitrary-precision integers with exact add and multiply.

Problem 148 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

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

struct Options {
    u64 rows = 1000000000ULL;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10ULL + static_cast<u64>(c - '0');
    }

    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--rows=", options.rows)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return true;
}

u128 count_not_divisible_by_seven(const u64 rows) {
    if (rows == 0) {
        return 0;
    }

    std::vector<int> digits;
    u64 x = rows;
    while (x > 0) {
        digits.push_back(static_cast<int>(x % 7ULL));
        x /= 7ULL;
    }
    std::reverse(digits.begin(), digits.end());

    std::vector<u128> pow28(static_cast<std::size_t>(digits.size() + 1), 1);
    for (std::size_t i = 1; i < pow28.size(); ++i) {
        pow28[i] = pow28[i - 1] * 28U;
    }

    u128 answer = 0;
    u128 prefix_product = 1;

    for (std::size_t i = 0; i < digits.size(); ++i) {
        const int d = digits[i];
        const std::size_t rem = digits.size() - i - 1;

        for (int xdigit = 0; xdigit < d; ++xdigit) {
            answer += prefix_product * static_cast<u128>(xdigit + 1) * pow28[rem];
        }
        prefix_product *= static_cast<u128>(d + 1);
    }

    return answer;
}

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string s;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        s.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

bool run_checkpoints() {
    if (to_string_u128(count_not_divisible_by_seven(100ULL)) != "2361") {
        std::cerr << "Checkpoint failed for first 100 rows" << '\n';
        return false;
    }
    if (to_string_u128(count_not_divisible_by_seven(7ULL)) != "28") {
        std::cerr << "Checkpoint failed for first 7 rows" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << to_string_u128(count_not_divisible_by_seven(options.rows)) << '\n';
    return 0;
}

Python

# Problem 148: Exploring Pascal's Triangle
# Count entries in first 10^9 rows of Pascal's triangle not divisible by 7.
# Use Lucas' theorem: base-7 digits.

def solve():
    rows = 10**9
    # Convert rows to base 7
    digits = []
    x = rows
    while x > 0:
        digits.append(x % 7)
        x //= 7
    digits.reverse()
    
    # For each digit d at position i, contribution from "full" blocks below
    # is d * 28^remaining * prefix_product, where prefix_product = prod(d_j+1) for j<i
    pow28 = [1] * (len(digits) + 1)
    for i in range(1, len(pow28)):
        pow28[i] = pow28[i-1] * 28
    
    answer = 0
    prefix_product = 1
    for i, d in enumerate(digits):
        rem = len(digits) - i - 1
        for xd in range(d):
            answer += prefix_product * (xd + 1) * pow28[rem]
        prefix_product *= (d + 1)
    
    print(answer)

solve()

Java

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

public class Euler148 {
    public static void main(String[] args) {
        long rows = 1000000000L;
        List<Integer> digits = new ArrayList<>();
        long x = rows;
        while (x > 0) {
            digits.add((int) (x % 7));
            x /= 7;
        }
        Collections.reverse(digits);
        BigInteger[] pow28 = new BigInteger[digits.size() + 1];
        pow28[0] = BigInteger.ONE;
        for (int i = 1; i < pow28.length; i++)
            pow28[i] = pow28[i - 1].multiply(BigInteger.valueOf(28));
        BigInteger answer = BigInteger.ZERO, pp = BigInteger.ONE;
        for (int i = 0; i < digits.size(); i++) {
            int d = digits.get(i);
            int rem = digits.size() - i - 1;
            for (int xd = 0; xd < d; xd++)
                answer = answer.add(pp.multiply(BigInteger.valueOf(xd + 1)).multiply(pow28[rem]));
            pp = pp.multiply(BigInteger.valueOf(d + 1));
        }
        System.out.println(answer);
    }
}