Detailed mathematical approach

Problem Summary

We are given \(p\) copies of \(A\), \(q\) copies of \(B\), and \(r\) copies of \(C\). A word is valid if every \(A\) and every \(B\) have at least two \(C\)'s between them. The task is to count all valid words and return the answer modulo \(10^9+7\).

The brute-force space has size \(\binom{p+q+r}{p,q,r}\), so direct enumeration is impossible for the real parameters. The key simplification is that the exact positions of the \(C\)'s matter only through how many times the word switches between \(A\) and \(B\) after all \(C\)'s are removed.

Mathematical Approach

Let \(W(p,q,r)\) denote the number of valid words built from \(p\) letters \(A\), \(q\) letters \(B\), and \(r\) letters \(C\).

Step 1: Remove All \(C\)'s and Study the \(A/B\) Skeleton

Set

$m=p+q.$

If we delete every \(C\) from a word, the remaining letters form a binary skeleton

$s_1s_2\dots s_m,\qquad s_i\in\{A,B\},$

with exactly \(p\) letters \(A\) and \(q\) letters \(B\). For such a skeleton define its transition count by

$t(s)=\#\{\,i\in\{1,\dots,m-1\}: s_i\ne s_{i+1}\,\}.$

This number \(t(s)\) counts how many adjacent boundaries in the skeleton change from \(A\) to \(B\) or from \(B\) to \(A\).

Step 2: Each Transition Forces Two \(C\)'s

Suppose two consecutive letters of the skeleton are different. In the full word, those two letters become an adjacent \(A/B\) pair once the \(C\)'s between them are ignored, so that boundary must contain at least two \(C\)'s. Otherwise those two letters would violate the rule immediately.

The converse is also true. If every transition boundary of the skeleton receives at least two \(C\)'s, then any \(A\) and any \(B\) in the whole word are separated by at least one such boundary, hence by at least two \(C\)'s in total.

Therefore a skeleton with \(t\) transitions consumes exactly

$2t$

mandatory letters \(C\). The whole constraint is reduced to a transition cost.

Step 3: Count Skeletons with a Fixed Number of Transitions

Let \(N_{p,q}(t)\) be the number of \(A/B\) skeletons with \(p\) letters \(A\), \(q\) letters \(B\), and exactly \(t\) transitions. A skeleton with \(t\) transitions has \(t+1\) runs.

If \(t=2u+1\) is odd, then the word starts and ends with different letters, so it has \(u+1\) runs of \(A\) and \(u+1\) runs of \(B\). Splitting \(p\) into \(u+1\) positive run lengths gives \(\binom{p-1}{u}\) choices, and similarly for \(q\). Since the skeleton may start with either \(A\) or \(B\),

$N_{p,q}(2u+1)=2\binom{p-1}{u}\binom{q-1}{u}.$

If \(t=2u\) is even, then the skeleton starts and ends with the same letter. Either \(A\) uses \(u+1\) runs and \(B\) uses \(u\) runs, or the roles are reversed, so

$N_{p,q}(2u)=\binom{p-1}{u}\binom{q-1}{u-1}+\binom{p-1}{u-1}\binom{q-1}{u}.$

As usual, we interpret \(\binom{n}{k}=0\) when \(k<0\) or \(k>n\).

Step 4: Distribute the Remaining \(C\)'s

Fix a skeleton with \(t\) transitions. After reserving \(2t\) mandatory \(C\)'s, there remain

$r-2t$

letters \(C\) to place freely. There are \(m+1\) slots: before the first skeleton letter, after the last one, and one slot between each consecutive pair of skeleton letters.

By the stars-and-bars formula, the number of ways to distribute the remaining \(C\)'s is

$\binom{(r-2t)+(m+1)-1}{(m+1)-1}=\binom{r-2t+m}{m},$

provided \(2t\le r\). So every skeleton with the same transition count contributes the same amount.

Step 5: Final Formula and the Natural Bound for \(t\)

If one of the letters \(A\) or \(B\) is absent, there is no restriction at all, so

$W(p,q,r)=\binom{r+m}{m}\qquad\text{when }p=0\text{ or }q=0.$

Otherwise

$W(p,q,r)=\sum_{t\ge 1} N_{p,q}(t)\binom{r-2t+m}{m},$

where terms with \(2t>r\) vanish automatically. Because the count is symmetric in \(p\) and \(q\), the implementation first swaps them so that \(p\le q\). Then the maximum possible transition count is

$t_{\max}=\min\left(m-1,\left\lfloor\frac{r}{2}\right\rfloor,\begin{cases} 2p-1,& p=q,\\ 2p,& p<q. \end{cases}\right).$

The last bound is purely combinatorial: the scarcer letter cannot support more alternations than this.

Worked Example: \((p,q,r)=(2,2,4)\)

Here \(m=4\). Since both \(A\) and \(B\) are present, we sum over transition counts.

For \(t=1\), the valid skeletons are \(AABB\) and \(BBAA\). Each needs \(2\) mandatory \(C\)'s, leaving \(2\) free \(C\)'s. The number of insertions is

$\binom{4-2+4}{4}=\binom{6}{4}=15,$

so the contribution is \(2\cdot 15=30\).

For \(t=2\), the valid skeletons are \(ABBA\) and \(BAAB\). Now all \(4\) letters \(C\) are forced, so the insertion factor is

$\binom{4-4+4}{4}=\binom{4}{4}=1,$

and the contribution is \(2\cdot 1=2\).

For \(t=3\), we would need \(6\) letters \(C\), but only \(4\) are available, so this case contributes nothing. Therefore

$W(2,2,4)=30+2=32,$

which matches the exact checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same formula. They first swap the counts so that \(p\le q\), compute \(m=p+q\), and handle the easy case \(p=0\) or \(q=0\) by returning \(\binom{r+m}{m}\) modulo \(10^9+7\).

Instead of building factorial tables up to \(r+m\), the implementation computes

$\binom{r+m}{m}=\prod_{i=1}^{m}\frac{r+i}{i}\pmod{10^9+7}$

using modular inverses of \(1,2,\dots,m\). It also builds the short binomial rows \(\binom{p-1}{u}\) and \(\binom{q-1}{u}\) incrementally, which is enough to evaluate the odd and even formulas for \(N_{p,q}(t)\).

The second important recurrence updates the insertion factor without recomputing a fresh binomial coefficient each time:

$\binom{n-2}{m}=\binom{n}{m}\cdot\frac{(n-m)(n-m-1)}{n(n-1)}.$

Starting from \(n=r+m\), one loop step moves from transition count \(t-1\) to \(t\). To make the divisions legal modulo \(10^9+7\), the implementation precomputes inverses for the consecutive denominators that appear in this recurrence.

Finally, it loops over \(t=1,\dots,t_{\max}\), evaluates the appropriate run-count formula for \(N_{p,q}(t)\), multiplies by \(\binom{r-2t+m}{m}\), and accumulates the result modulo \(10^9+7\).

Complexity Analysis

After the swap, let \(m=p+q\) and \(t_{\max}\) be the transition limit above. Precomputing inverses up to \(m\) costs \(O(m)\) time and memory. The short binomial tables cost \(O(t_{\max})\), and the final summation over all transition counts also costs \(O(t_{\max})\).

Hence the total complexity is

$O(m+t_{\max})=O(p+q)$

time and

$O(m+t_{\max})=O(p+q)$

memory. The large value of \(r\) does not create a table of size \(r\); it appears only inside modular products.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=873
2. Stars and bars: Wikipedia — Stars and bars
3. Compositions of integers: Wikipedia — Composition (combinatorics)
4. Binomial coefficient: Wikipedia — Binomial coefficient
5. Modular arithmetic: Wikipedia — Modular arithmetic