## Let $B(n) = \displaystyle \prod_{k=0}^n {n \choose k}$, a product of binomial coefficients.

For example, $B(5) = {5 \choose 0} \times {5 \choose 1} \times {5 \choose 2} \times {5 \choose 3} \times {5 \choose 4} \times {5 \choose 5} = 1 \times 5 \times 10 \times 10 \times 5 \times 1 = 2500$.

Let $D(n) = \displaystyle \sum_{d|B(n)} d$, the sum of the divisors of $B(n)$.

For example, the divisors of B(5) are 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500, 625, 1250 and 2500,

so D(5) = 1 + 2 + 4 + 5 + 10 + 20 + 25 + 50 + 100 + 125 + 250 + 500 + 625 + 1250 + 2500 = 5467.

Let $S(n) = \displaystyle \sum_{k=1}^n D(k)$.

You are given $S(5) = 5736$, $S(10) = 141740594713218418$ and $S(100)$ mod $1\,000\,000\,007 = 332792866$.

Find $S(20\,000)$ mod $1\,000\,000\,007$.

### To find the value of $S(20,000)$ mod $1,000,000,007$, we will first need to calculate the values of $S(6)$, $S(7)$, $S(8)$, $S(9)$, $S(10)$ (already given), $S(11)$, $S(12)$, $S(13)$, $S(14)$, $S(15)$, $S(16)$, $S(17)$, $S(18)$, $S(19)$, and $S(20)$.

Then we can use these values to calculate $S(20,000)$ using dynamic programming.

First, let’s write a function to calculate the binomial coefficient:

“`python

def binomial_coefficient(n, k):

if k == 0 or k == n:

return 1

else:

return binomial_coefficient(n-1, k-1) + binomial_coefficient(n-1, k)

“`

Next, we will define a helper function to calculate the product of binomial coefficients, $B(n)$:

“`python

def B(n):

product = 1

for k in range(n+1):

product *= binomial_coefficient(n, k)

return product

“`

Now, let’s define the function to calculate the sum of divisors, $D(n)$:

“`python

def D(n):

divisors = []

number = B(n)

for i in range(1, int(number**0.5) + 1):

if number % i == 0:

divisors.append(i)

if i != number // i:

divisors.append(number // i)

return sum(divisors)

“`

Next, we will define the cumulative sum function, $S(n)$:

“`python

def S(n):

cumulative_sum = 0

for k in range(1, n+1):

cumulative_sum += D(k)

return cumulative_sum

“`

Now, let’s calculate the values of $S(6)$ to $S(20)$:

“`python

values = [5736] # S(5)

for k in range(6, 21):

values.append(S(k))

“`

Finally, we can calculate $S(20,000)$ using dynamic programming:

“`python

mod = 10**9 + 7

def calculate_S(n):

cumulative_sum = sum(values[:n])

for k in range(21, n+1):

cumulative_sum += D(k)

cumulative_sum %= mod

return cumulative_sum

result = calculate_S(20000)

“`

The final result stored in the `result` variable will give the value of $S(20,000)$ mod $1,000,000,007$.

Note: Calculating $S(20,000)$ might take some time as it involves a large number of calculations.

##### More Answers:

Linear Transformations of Polygonal NumbersSkipping Squares

Low-Prime Chessboard Nim