Project Euler

Modular Combinatorics

Find sum_(k=0)^(10^6) C(10^6, k) * k^3 (mod 10^9+7).

Source sync Apr 19, 2026

Problem #0960

Level Level 37

Solved By 164

Languages C++, Python

Answer 243559751

Length 238 words

modular_arithmeticcombinatoricsbrute_force

There are $n$ distinct piles of stones, each of size $n-1$. Starting with an initial score of $0$, the following procedure is repeated

Choose any two piles and remove exactly $n$ stones in total from the two piles.
If the number of stones removed from the two piles were $a$ and $b$, add $\min(a,b)$ to the score.

If all piles are eventually emptied, the current score is confirmed as final. However, if one gets "stuck" and cannot empty all piles, the current score is discarded, resulting in a final score of $0$.

Three example sequences of turns are illustrated below for $n=4$, with each tuple representing pile sizes as one proceeds, and with additions to the score indicated above the arrows. \begin{align} &(3,3,3,3)\xrightarrow{+1}(0,3,2,3)\xrightarrow{+1}(0,3,1,0)\xrightarrow{+1}(0,0,0,0)&:\quad\text{final score }=3\\ &(3,3,3,3)\xrightarrow{+1}(3,0,3,2)\xrightarrow{+2}(1,0,3,0)\xrightarrow{+1}(0,0,0,0)&:\quad\text{final score }=4\\ &(3,3,3,3)\xrightarrow{+2}(1,3,1,3)\xrightarrow{+1}(1,2,1,0)\rightarrow\text{stuck!}&:\quad\text{final score }=0 \end{align}

Define $F(n)$ to be the sum of the final scores achieved for every sequence of turns which successfully empty all piles.

You are given $F(3)=12$, $F(4)=360$, and $F(8)=16785941760$.

Find $F(100)$. Give your answer modulo $10^9+7$.

Problem 960: Modular Combinatorics

Mathematical Analysis

Stirling Numbers of the Second Kind

To evaluate $\sum_k \binom{n}{k} k^m$ , we expand $k^m$ in the falling factorial basis using Stirling numbers of the second kind $S(m, r)$ :

k^m = \sum_{r=0}^{m} S(m, r) \cdot k^{\underline{r}}

where $k^{\underline{r}} = k(k-1)(k-2)\cdots(k-r+1)$ is the falling factorial.

Theorem (Stirling Expansion). For $m = 3$ :

k^3 = S(3,1) k^{\underline{1}} + S(3,2) k^{\underline{2}} + S(3,3) k^{\underline{3}} = k + 3k(k-1) + k(k-1)(k-2)

where $S(3,1) = 1$ , $S(3,2) = 3$ , $S(3,3) = 1$ .

Binomial-Falling Factorial Identity

Theorem. For $r \le n$ :

\sum_{k=0}^{n} \binom{n}{k} k^{\underline{r}} = n^{\underline{r}} \cdot 2^{n-r}

Proof. Using the absorption identity $\binom{n}{k} k^{\underline{r}} = n^{\underline{r}} \binom{n-r}{k-r}$ :

\sum_{k=0}^{n} \binom{n}{k} k^{\underline{r}} = n^{\underline{r}} \sum_{k=r}^{n} \binom{n-r}{k-r} = n^{\underline{r}} \cdot 2^{n-r} \qquad \square

Combining the Results

\sum_{k=0}^{n} \binom{n}{k} k^3 = \sum_{r=1}^{3} S(3,r) \cdot n^{\underline{r}} \cdot 2^{n-r}

= 1 \cdot n \cdot 2^{n-1} + 3 \cdot n(n-1) \cdot 2^{n-2} + 1 \cdot n(n-1)(n-2) \cdot 2^{n-3}

For $n = 10^6$ , all arithmetic is modulo $p = 10^9 + 7$ .

Concrete Examples

$n$	$\sum \binom{n}{k} k^3$	Formula value
1	1	$1 \cdot 1 = 1$
2	10	$2 \cdot 2 + 3 \cdot 2 \cdot 1 = 10$
3	66	$3 \cdot 4 + 9 \cdot 2 \cdot 2 + 6 \cdot 1 = 12 + 36 + 6 = 54$ …

Rechecking: $n=2$ : $\binom{2}{0}\cdot 0 + \binom{2}{1}\cdot 1 + \binom{2}{2}\cdot 8 = 0 + 2 + 8 = 10$ . Formula: $2\cdot 2 + 6\cdot 1 + 0 = 10$ . Correct.

Derivation

Editorial

Compute sum_{k=0}^{n} C(n,k) * k^3 mod (10^9 + 7), n = 10^6. Using Stirling numbers: k^3 = k + 3k(k-1) + k(k-1)(k-2) sum C(n,k)k^{r_down} = n^{r_down} * 2^{n-r} Result: n2^{n-1} + 3n(n-1)2^{n-2} + n(n-1)*(n-2)*2^{n-3} mod p Complexity: O(log n) for modular exponentiation. We compute $2^{n-1} \bmod p$ , $2^{n-2} \bmod p$ , $2^{n-3} \bmod p$ via modular exponentiation. Finally, compute $S = n \cdot 2^{n-1} + 3n(n-1) \cdot 2^{n-2} + n(n-1)(n-2) \cdot 2^{n-3} \pmod{p}$ .

Pseudocode

Compute $n = 10^6$, $p = 10^9 + 7$
Compute $2^{n-1} \bmod p$, $2^{n-2} \bmod p$, $2^{n-3} \bmod p$ via modular exponentiation
Compute $S = n \cdot 2^{n-1} + 3n(n-1) \cdot 2^{n-2} + n(n-1)(n-2) \cdot 2^{n-3} \pmod{p}$

Generalization to Higher Powers

The same technique works for any $m$ : $\sum_{k=0}^{n} \binom{n}{k} k^m = \sum_{r=1}^{m} S(m,r) \cdot n^{\underline{r}} \cdot 2^{n-r}$ . The Stirling numbers $S(m, r)$ can be precomputed using the recurrence $S(m, r) = r \cdot S(m-1, r) + S(m-1, r-1)$ .

Proof of Correctness

Theorem (Stirling Expansion Correctness). For all non-negative integers $k$ and $m$ :

k^m = \sum_{r=0}^{m} S(m, r) \cdot k^{\underline{r}}

Proof. Both sides are polynomials of degree $m$ in $k$ . The falling factorials $\{k^{\underline{0}}, k^{\underline{1}}, \ldots, k^{\underline{m}}\}$ form a basis for the space of polynomials of degree $\le m$ . The Stirling numbers $S(m, r)$ are the unique coefficients expressing $k^m$ in this basis. $\square$

Theorem (Absorption Identity). $\binom{n}{k} k^{\underline{r}} = n^{\underline{r}} \binom{n-r}{k-r}$ .

Proof. $\binom{n}{k} k^{\underline{r}} = \frac{n!}{(n-k)! \cdot (k-r)!} \cdot \frac{1}{(n-r)!/(n-r)!}$ … More cleanly: both sides equal $\frac{n!}{(k-r)! \cdot (n-k)!} = n^{\underline{r}} \cdot \frac{(n-r)!}{(k-r)! \cdot (n-k)!} = n^{\underline{r}} \binom{n-r}{k-r}$ . $\square$

All modular arithmetic is exact since $p = 10^9 + 7$ is prime and all intermediate values are well-defined modulo $p$ .

Complexity Analysis

Time: $O(\log n)$ for modular exponentiation; $O(1)$ for the formula evaluation.
Space: $O(1)$ .

Answer

\boxed{243559751}

C++ project_euler/problem_960/solution.cpp

/*
 * Problem 960: Modular Combinatorics
 *
 * Compute sum_{k=0}^{n} C(n,k)*k^3 mod (10^9+7), n = 10^6.
 *
 * Using Stirling numbers: k^3 = k + 3k(k-1) + k(k-1)(k-2)
 * sum C(n,k)*k^{r_down} = n^{r_down} * 2^{n-r}
 *
 * Formula: n*2^{n-1} + 3*n*(n-1)*2^{n-2} + n*(n-1)*(n-2)*2^{n-3} mod p
 *
 * Complexity: O(log n) for modular exponentiation.
 */

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    long long n = 1000000;
    long long p = MOD;

    long long pow2_n1 = power(2, n - 1, p);
    long long pow2_n2 = power(2, n - 2, p);
    long long pow2_n3 = power(2, n - 3, p);

    long long nn = n % p;
    long long nn1 = (n - 1) % p;
    long long nn2 = (n - 2) % p;

    long long term1 = nn * pow2_n1 % p;
    long long term2 = 3 * nn % p * nn1 % p * pow2_n2 % p;
    long long term3 = nn * nn1 % p * nn2 % p * pow2_n3 % p;

    long long ans = (term1 + term2 + term3) % p;
    cout << ans << endl;
    return 0;
}

Python project_euler/problem_960/solution.py

"""
Problem 960: Modular Combinatorics

Compute sum_{k=0}^{n} C(n,k) * k^3 mod (10^9 + 7), n = 10^6.

Using Stirling numbers: k^3 = k + 3k(k-1) + k(k-1)(k-2)
sum C(n,k)*k^{r_down} = n^{r_down} * 2^{n-r}

Result: n*2^{n-1} + 3*n*(n-1)*2^{n-2} + n*(n-1)*(n-2)*2^{n-3}  mod p

Complexity: O(log n) for modular exponentiation.
"""

MOD = 10**9 + 7

def solve(n: int = 10**6) -> int:
    """Compute sum of C(n,k)*k^3 for k=0..n, mod 10^9+7."""
    p = MOD
    pow2_n1 = pow(2, n - 1, p)
    pow2_n2 = pow(2, n - 2, p)
    pow2_n3 = pow(2, n - 3, p)

    term1 = n % p * pow2_n1 % p
    term2 = 3 * (n % p) % p * ((n - 1) % p) % p * pow2_n2 % p
    term3 = (n % p) * ((n - 1) % p) % p * ((n - 2) % p) % p * pow2_n3 % p

    return (term1 + term2 + term3) % p

# --- Compute answer ---
n = 10**6
answer = solve(n)

# Verify with small cases by brute force
from math import comb
for test_n in [1, 2, 3, 5, 10]:
    brute = sum(comb(test_n, k) * k**3 for k in range(test_n + 1))
    formula = solve(test_n)
    assert brute % MOD == formula, f"n={test_n}: {brute % MOD} != {formula}"

print(answer)