We scale so that \(L=1\). For convenience, we think of the range as \([-K,0]\).

Consider when the numbers written on the red balls are fixed as \(r_1<r_2<\cdots<r_N\).

Let the numbers written on the blue balls be \(b_1 < b_2<\cdots<b_N\). The condition to satisfy is \(r_i \leq b_i\). When deciding \(b_i\) from smallest to largest, we find that we need to compute the following integral:

• \(f_0(x)=1\)
• \(f_i(x)=\int_{t=r_i}^{x} f_{i-1}(t) dt\) (\(1 \leq i \leq N\))
• \(f_N(0)\) is the answer.

Since all \(f_i(x)\) are polynomials, we can think of this as giving a recurrence for their coefficients.

Let \(a_i=f_i(0)\), and summarize the recurrence for \(a_0,\cdots,a_N\) as follows:

• \(a_0=1\)
• \(a_i=- \sum_{j=0}^{i-1}a_{j} \times r_i^{i-j}/(i-j)!\)

Let us reverse the order of the DP. Setting \(q_i=r_{N-i}\), we want to compute the following sequence \(b\):

• \(b_0=1\)
• \(b_i=- \sum_{j=0}^{i-1}b_j \times q_j^{i-j}/(i-j)!\)

Here, consider the generating function \(g(x)=\sum_{0 \leq i \leq N} b_i x^i\) of \(b\).

Then, \(\sum_{0 \leq i \leq N} b_i x^i \exp(q_ix) \equiv 1 \mod x^{N+1}\).

Incidentally, \(q_i\) is not fixed and there are \(M\) candidates. Considering similar DP with candidates \(v_{i,1},\cdots,v_{i,M}\) for \(q_i\), the following equation holds:

• \(\sum_{0 \leq i \leq N} b_i x^i (\frac{1}{M}\sum_{1 \leq j \leq M}\exp(v_{i,j}x)) \equiv 1 \mod x^{N+1}\)

Incidentally, \(v_{i,j}=(A_j-1)-i\). Thus,

• \(\sum_{0 \leq i \leq N} b_i x^i \exp(-ix) (\frac{1}{M}\sum_{1 \leq j \leq M}\exp((A_j-1)x)) \equiv 1 \mod x^{N+1}\)

Here, let \(V(x)=(\frac{1}{M}\sum_{1 \leq j \leq M}\exp((A_j-1)x))\). Then, \(V(x) g(x \exp(-x)) \equiv 1 \mod x^{N+1}\).

Let \(W(x)\) be the compositional inverse of \(x \exp(-x)\). Then,

• \(g(x)=1/V(W(x)) \equiv 1 \mod x^{N+1}\)

Now, we just need to compute this.

The computation of \(V(X)\) can be reduced to computing \(\sum_{1 \leq j \leq M} \frac{1}{1-(A_j-1)x}\) by divide-and-conquer + FFT.

The remaining part is FPS composition and compositional inverse itself.

The overall time complexity is \(O(M \log^2 M + N \log^2N)\).

The compositional inverse can be omitted by computing \(W(x)=\sum_{1 \leq i} i^{i-1}/i! x^i\) by hand.

Sample solution (C++)