Overview

We reduce the problem of counting the number of ways to choose exactly \(K\) plots from \(N\) plots such that no two chosen plots are adjacent to a combinatorial formula, computed modulo \(10^9+7\).

Analysis

Since “adjacent selections are forbidden,” there must be at least one empty plot between any two chosen plots. A naive DP approach of “choose or skip from left to right” would require tracking “how many have been chosen so far” in the state, resulting in \(O(NK)\) complexity, which is far too slow for \(N\le 10^6\).

The key observation here is that the answer is simply the binomial coefficient \(\binom{N-K+1}{K}\).

Why the answer is \(\binom{N-K+1}{K}\)

Let the chosen plots in ascending order be \(a_1 < a_2 < \dots < a_K\). The no-adjacent constraint requires [ a_{i+1} \ge a_i + 2 ]

To eliminate the “at least one gap between consecutive choices” constraint, we apply the following transformation: [ b_i = a_i - (i-1) ] Then: - \(b_1 \ge 1\) - \(b_K \le N-(K-1)=N-K+1\) - Furthermore, from \(a_{i+1}\ge a_i+2\): [ b{i+1} = a{i+1}-i \ge (a_i+2)-i = (a_i-(i-1)) + 1 = b_i + 1 ] Therefore \(b_1 < b_2 < \dots < b_K\) (this is simply “choosing \(K\) distinct numbers”).

In other words, there is a one-to-one correspondence with choosing \(K\) distinct numbers from \(1\) to \(N-K+1\), so [ \text{answer} = \binom{N-K+1}{K} ]

Also, for a valid selection to exist, the minimum arrangement (\(1,3,5,\dots\)) must fit, which requires [ N \ge 2K-1 \iff N-K+1 \ge K ] If this is not satisfied, the answer is \(0\) (the if n < K: check in the code).

(Example) When \(N=5, K=2\), we have \(n=N-K+1=4\), so the answer is \(\binom{4}{2}=6\). Indeed, the valid selections are \(\{1,3\},\{1,4\},\{1,5\},\{2,4\},\{2,5\},\{3,5\}\) — exactly 6 ways.

Algorithm

1. Set \(n = N-K+1\).
2. If \(n < K\), it is impossible, so output \(0\).
3. Otherwise, the answer is \(\binom{n}{K}\).
4. Since \(\bmod = 10^9+7\) is prime, precompute factorials and inverse factorials to calculate [ \binom{n}{K} \equiv \frac{n!}{K!(n-K)!} \pmod{\bmod} ]
   • The modular inverse is computed using Fermat’s little theorem: \(a^{-1}\equiv a^{\bmod-2}\pmod{\bmod}\), via pow(a, MOD-2, MOD).

Complexity

• Time complexity: \(O(n)\) (precomputation of factorials and inverse factorials)
• Space complexity: \(O(n)\) (fact and invfact arrays)

Implementation Details

• Since we need factorials up to \(n = N-K+1\), the array size is n+1.

• For inverse factorials, compute invfact[n] = fact[n]^{-1} with a single pow call, then fill backwards using [ (i-1)!^{-1} = i!^{-1}\cdot i ] This is efficient.

• Check the impossibility condition \(n<K\) (i.e., \(N<2K-1\)) at the beginning for early termination.

  Source Code

import sys

MOD = 10**9 + 7

def modinv(a):
    return pow(a, MOD - 2, MOD)

def main():
    N, K = map(int, sys.stdin.readline().split())
    n = N - K + 1
    if n < K:
        print(0)
        return

    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD

    invfact = [1] * (n + 1)
    invfact[n] = modinv(fact[n])
    for i in range(n, 0, -1):
        invfact[i - 1] = invfact[i] * i % MOD

    ans = fact[n] * invfact[K] % MOD * invfact[n - K] % MOD
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.