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 {\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}=\{\begin{array}{ll}{\displaystyle \frac{n!}{k!\times (n-k)!}}& \text{if }0\le k\le n\\ 0& \text{if }k<0\text{ or }k>n\end{array}}$$

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

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(\mathrm{mod}{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(\mathrm{mod}{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 ${\displaystyle (\genfrac{}{}{0ex}{}{N}{k})}modM$. We can instead find:

$${\displaystyle (N!\times (k!{)}^{{10}^8+5}\times ((N-k)!{)}^{{10}^8+5})modM}$$

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 {\displaystyle (\genfrac{}{}{0ex}{}{N}{i-1})}\times \frac{N-i+1}{i}={\displaystyle (\genfrac{}{}{0ex}{}{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 ${\displaystyle (\genfrac{}{}{0ex}{}{N}{i})}={\displaystyle (\genfrac{}{}{0ex}{}{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.