PROBLEM LINK:
Author: Pavel Sheftelevich
Tester: Mahbubul Hasan and Sunny Aggarwal
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng
DIFFICULTY:
Easy
PREREQUISITES:
Combinatorics, DP
PROBLEM:
You have to fill a N x M matrix with non negative numbers such that the sum of numbers at row i (2 \le i \le N) is greater than or equal to the sum of numbers in row i  1.
SHORT EXPLANATION
Suppose we want to fill one row (which has M elements) such that the sum of the numbers is X. The number of ways to fill this row can be obtained using a standard combinatorics formulae: \binom{X + M  1}{M  1}.
We can solve using dp: let solve(i, x) denote the number of ways to fill the matrix such that the matrix is steady and the sum of the i^{th} row is x. We can easily solve this using the recurrance:
solve(i, x) = solve(i + 1, x) * \binom{x + m  1}{m  1} + solve(i, x + 1)
EXPLANATION:
Suppose we start at row 1. Say, we fill this row such that the sum is x. Now when we move on to the second row, we must make sure that the sum of the second row is greater than or equal to x. So, besides the row itself, we must also keep track of the minimum sum of the row.
Let solve(i, x) be the number of ways to fill the matrix from i^{th} row to the N^{th} row such that the matrix is steady and the sum of i^{th} row is at least x. There are now two ways to proceed

We make the sum of current row x: We need to calculate in how many ways we can make the sum of the current row x. There are M elements in this rowee. So we need to find the number of ways in which we can choose M numbers such that they sum up to x. This can be calculated using the formula \binom{X + M  1}{M  1}. See TODO for an explanation.

We don’t make the sum of current row x: In this case we can make the sum of the row atleast x + 1.
Putting this together we have the following solution
MOD = 1000000000
Preprocess array C such that C[n][k] = n choose k mod MOD
Solve(i, x):
See if we have already calculated the answer for this input and if so return the value
Edge cases:
if x > M return 0 // Sum of a row can't be greater than M
if i == N + 1 return 1
ret = (Solve(i + 1, x) * C[x + m  1][m  1] + Solve(i, x + 1)) mod MOD
Answer is Solve(1, 0)
Time Complexity:
We calculate each state only once. For each state we take a constant amount of time. We know that i can take values till N while x can take values till M. So, the total amount of time taken for solve will be O(NM).