The table in the problem is called a histogram. We need to count the number of ways to separate the gases into ~K~ cells in the histogram ~H~, according to the rules outlined in the problem statement. Let that number be ~dp(H, K)~. We can calculate it recursively.

Find the height of the lowest column in ~H~ and call it ~h~.

There are three cases:

1. All columns are of height ~0~ – the histogram is empty. Therefore: $$\displaystyle dp(H, K) = \begin{cases} 1 & \text{for }K = 0 \\ 0 & \text{for }K > 0 \end{cases}$$

2. ~h = 0~. There is a column of height zero, which means that we can split the histogram into two sub-histograms ~H_L~ and ~H_R~ (left and right of the zero-height column). We can independently calculate the number of ways to put gases into the two histograms, combining the results: $$\displaystyle dp(H, K) = \sum_{k=0}^K dp(H_L, k) \cdot dp(H_R, K-k)$$

3. ~h > 0~. There is a rectangle ~R~ of height ~h~ that is as wide as the histogram (call this width ~w~). We will solve this case by counting how many ways we can put ~k~ gases into rectangle ~R~, the remaining ~K-k~ gases going into the sub-histogram ~H_U~ (which is ~H~ without ~R~). We can choose the rows into which to put gases in ~\binom h k~ ways and permute them in ~k!~ ways. Then we can choose the columns in ~\binom{w-(K-k)}{k}~ ways, because ~K-k~ columns are already occupied by gases above, in sub-histogram ~H_U~. $$\displaystyle dp(H, K) = \sum_{k=0}^K \frac{h!}{(h-k)!} \binom{w-(K-k)}{k} dp(H_U, K-k)$$

The total number of different histograms that will occur as the parameter in the recursion is in linear proportion to the width of the histogram: a recursive call in case 3 always yields a case 2 histogram, which reduced the histogram in width.

For a full score, it is also required to efficiently calculate the binomial coefficients.