Let ~F_{n, k}~ be the total cost of a unit with size ~n~ and tier ~k~.

For 20% of the points, you should notice that

~F_{n, k} = \displaystyle\sum_{i = 1}^{n} F_{i, k - 1}~ but ~F_{n - 1, k} = \displaystyle\sum_{i = 1}^{n - 1} F_{i, k - 1}~ so ~F_{n, k} = F_{n - 1, k} + F_{n, k - 1}~.

If you store all the values of ~F_{n, k}~ in an array as you go along, you can compute ~F_{N, K}~ this in ~O(NK)~ time.

For the rest of the points, you should notice that ~F_{n, k}~ is just ~\dbinom{n + k - 1}{k} = \dbinom{n + k - 1}{n - 1}~.

There are a few interpretations for why this is the case, including

• The formula ~F_{n, k} = F_{n - 1, k} + F_{n, k - 1}~ is the same as the formula for Pascal's Triangle, rotated by 45 degrees
• This is equivalent to a combinatorics problem that can be solved using Stars and Bars
• The "Hockey Stick" Identity

Of course, during contest it's enough to just write down a few values of ~F_{n, k}~ and find that it matches Pascal's Triangle by inspection, but for fun, you can try to prove this formula on you own.

To compute ~\dbinom{n}{k}~ modulo ~M~ in general, you can use the formula ~\dbinom{n}{k} = \dfrac{n!}{k!(n - k)!}~.

Computing ~n!~ modulo ~M~ is easy; just loop and multiply, making sure to take the modulo at each step to prevent overflow.

However, dividing by a number and getting the result modulo ~M~ is harder.

Let ~0 \leq a < M~ be an integer. We say that ~x~ is a modular multiplicative inverse of ~a~ if ~ax = 1~, modulo ~M~. Note that for any number ~n~ divisible by ~a~, ~nx = \frac{x}{a}~.

It turns out that if ~M~ is prime, the modular multiplicative inverse of a number is unique and can be found by the formula ~x = a^{M - 2}~, modulo ~M~. This is a direct result of Fermat's Little Theorem.

Calculating ~a^{M - 2}~ modulo ~M~ is possible in ~O(\log M)~ time using fast exponentiation.