For the first subtask, it is enough to generate the ~N^{th}~ row of Pascal's Triangle, then print out the elements of the row modulo ~M~. Alternatively, you can use the formula for the combination, and then print this number modulo ~M~. The formula for the combination is given below:

$$\displaystyle \dbinom{n}{k}=\begin{cases} \dfrac{n!}{k! \times (n-k)!} & \text{if } 0 \le k \le n \\ 0 & \text{if } k < 0 \text{ or } k > n \end{cases}$$

$$\displaystyle n!=\begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n \ge 1 \end{cases}$$

Time Complexity: Slower than ~\mathcal{O}(N^2)~

For the second subtask, it is enough to generate the ~N^{th}~ row of Pascal's Triangle by storing the elements of each previous row modulo ~M~. Alternatively, you can use the formula for the combination in a data type that supports arbitrary-precision integers, such as Java's BigInteger or Python's normal integer, then print this number modulo ~M~.

Time Complexity: ~\mathcal{O}(N^2)~

For the third subtask, we first notice that ~M~ is prime and ~M>N~. This means that no number in the ~N^{th}~ row is divisible by ~M~. Since ~M~ is prime, we can use Fermat's Little Theorem to get the multiplicative inverse. If ~x~ is not divisible by ~M~, then ~x^{10^8+5} \times x \equiv 1 \pmod{10^8+7}~, and we have that ~x^{10^8+5}~ is the multiplicative inverse of ~x~.

Why do we need the multiplicative inverse? Suppose that you have ~A \times x \times B~, you know the value of ~x~, and you want to find ~A \times B~. You would compute ~(A \times x \times B) \times x^{10^8+5} \equiv (A \times B) \times (x \times x^{10^8+5}) \equiv A \times B \pmod{10^8+7}~. To divide by ~x~, you instead multiply by ~x^{10^8+5}~.

Next, suppose that we have already computed ~0!, 1!, \dots, N!~ modulo ~M~ and we want to find ~\dbinom{N}{k} \bmod M~. We can instead find:

$$\displaystyle \left(N! \times (k!)^{10^8+5} \times ((N-k)!)^{10^8+5}\right) \bmod M$$

The time complexity of this computation is ~\mathcal{O}(\log M)~, and you should repeat this computation ~N+1~ times.

Make sure that 64-bit integers are used, and no overflows will occur.

Time Complexity: ~\mathcal{O}(N \log M)~

The fourth subtask is a distraction. This time, we could have ~M<N~, and this would result in some elements being divisible by ~M~. I have found a few online articles that point to Lucas's Theorem, which could be helpful.

For the fifth subtask, we will first look at the relationship between two adjacent combinations.

$$\displaystyle \dbinom{N}{i-1} \times \frac{N-i+1}{i} = \dbinom{N}{i}$$

The proof of this relationship is very boring. I recommend that you try to prove it! Hint: expand everything.

A combination can always be factored as a product of prime numbers. Also, two adjacent combinations share many of the same prime factors. We want to create a multiset that supports these 3 operations:

• Insert a prime number
• Erase an existing number in the multiset
• Calculate the product of the numbers in the multiset modulo ~M~

This data structure is easiest to implement as a segment tree, although a BBST should also work fine too.

In total, around ~\mathcal{O}(N \log N)~ prime numbers will be inserted/erased in the data structure (there is probably a better bound, but this is good enough). Each insert/erase operation will take ~\mathcal{O}(\log N)~ time to update the product (this time complexity can be improved).

Time Complexity: ~\mathcal{O}(N \log^2 N)~, or slightly better

Note 1: If you have trouble passing this problem, you may find ~\dbinom{N}{i} = \dbinom{N}{N-i}~ useful. In the best case, this optimization will cut your runtime in half.

Note 2: Some programmers have found a way to solve this problem using FFT. I may include an analysis of this approach later.