While the problem statement distinguishes the \((M-K)\) people who is not seated yet, but we may not distinguish them while calculation and finally multiply the coefficient. Hereinafter we do not distinguish those who is not seated yet.

First, we compute the following values.

\(f_1(n,k) :=\) The sum of scores over all cases where someone is already sitting on the both ends of the \(n\) chairs and \(k\) more people is going to sit
\(f_2(n,k) :=\) The sum of scores over all cases where someone is already sitting on the left ends of the \(n\) chairs and \(k\) more people is going to sit
\(f_3(n,k) :=\) The sum of scores over all cases where \(k\) people is sitting on \(n\) empty chairs

We will introduce two ways to compute \(f_1(n,k)\).

---

Solution using formal power series

If you know little about formal power series, we recommend you to read the editorial of formal power series written by maspy (in Japanese) first.

We will denote “the coefficient of degree \(n\) of polynomial \(F\)” by \([x^n]F\).

We will consider \(f_1(n,k)\). Since

\(\displaystyle f_1(n,k) = \sum_{i=0}^{n-1} [x^i] \{(x + 2x^2 + 3x^3 + \cdots)^k (n-1-i) \}\),

using relations like

\(\displaystyle \frac{1}{(1-T)^k} = \sum_{n=0}^{\infty} \left( \begin{matrix} n+k-1 \\ k-1 \end{matrix} \right) T^n\),

we have

\(\displaystyle f_1(n,k)\)

\(\displaystyle= \sum_{i=0}^{n-1} [x^i] \{(x + 2x^2 + 3x^3 + \cdots)^k (n-1-i) \} \)

\(\displaystyle=[x^{n-1}] (x + 2x^2 + 3x^3 + \cdots)^{k+1}\)

\(\displaystyle=[x^{n-k-2}] (1 + 2x + 3x^2 + \cdots)^{k+1}\)

\(\displaystyle=[x^{n-k-2}] \frac{1}{(1-x)^{2k+2}} \)

\(\displaystyle=\left( \begin{matrix} n+k-1 \\ 2k+1 \end{matrix} \right)\)

so we could find \(f_1(n,k)\).

---

Solution in combinatorial terms

There are \((n+k+1)\) chairs. \((k+2)\) people will sit on them. The chairs in both ends should be occupied by people. Moreover, \((k+1)\) balls will be placed between people. A ball and a person can be placed to a single chair simultaneously.
How many placements are possible?

The answer for the problem above and \(f_1(n,k)\) are equal.
In other words, the problem is equivalent to

How many ways are there to choose \(2k+1\) sites from \(n+k-1\) chairs?

which is equal to \(\left( \begin{matrix} n+k-1 \\ 2k+1 \end{matrix} \right)\).

Therefore, we could find \(f_1(n,k)\).

---

With similar discussion we can obtain

\(f_2(n,k) = \left( \begin{matrix} n+k-1 \\ 2k \end{matrix} \right) \),

\(f_3(n,k) = \left( \begin{matrix} n+k-1 \\ 2k-1 \end{matrix} \right)\).

---

Back to the original problem.

When \(K=0\), we can use \(f_3\).

When \(K \neq 0\), it boils down to the following problem, where \(f_1\) and \(f_2\) are used as the coefficients of polynomials.

Given are \(K+1\) polynomials. The sum of degrees is \(N-k\). What is the coefficient of degree \((M-K)\) of their product?

We compute the product recursively with divide-and-conquer method.
Here, the divide-and-conquer consists of \(O(\log K)\) steps, and the complexity per step is \(O(N \log M)\) if we use convolution of ACL (AtCoder Library), so the problem has been solved in a total of \(O(N \log M \log K)\) time.

When implementing, we think it is easy to adopt an algorithm where all the polynomials are added to a deque, and while the deque has two or more elements, “take the first two polynomials and push their product at back.”