Where it runs
1. The problem
Step 136 raised a number to a big power fast. Step 137 kept numbers small with a modulus (the remainder after division). Now the count itself is the answer. You have n things. How many ways are there to pick r of them, when the order does not matter?
This is written C(n, r) and read "n choose r". Pick 2 friends out of 5 to invite: C(5, 2) = 10. Deal 5 cards out of 52: C(52, 5) = 2,598,960. The school formula is n! / (r! · (n - r)!). Here n! (read "n factorial") means 1·2·3·...·n, all the numbers up to n multiplied together.
That formula has a trap. n! grows huge very fast. 13! is already more than 6 billion. 21! is bigger than a 64-bit integer can hold. 52! has 68 digits. If you compute the three factorials separately, the numbers overflow (grow too big to store) long before the division brings the answer back down to a small number such as 2,598,960.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Counting problems that need n choose r, such as paths in a grid, sorted strings or orders that keep a shape. Pascal's triangle adds two numbers per cell, so no huge factorial ever appears, and it works modulo 10^9 + 7 too.
Build the triangle row by row. It is the lesson's table itself.
Only one row is needed, so update a single array from right to left.
A sorted string of length n over 5 vowels is a choice with repeats, C(n + 4, 4), read straight off the triangle.
With d as the distance, you need (k + d) / 2 steps right out of k, so the answer is C(k, (k + d) / 2) modulo 10^9 + 7, or 0 when d is above k or the parity is wrong.
The left and right subtrees can interleave in C(left + right, left) ways, so multiply that by both subtrees' answers and subtract 1 at the end.