Show problems as
Classic problem #4002MediumMathCombinatorics

Count Valid Sequences

Real-world version: Placing k Markers With None Adjacent
Tracked in this browser only
Read Count Valid Sequences on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A strip has n slots in a row, and k markers are to be placed in them, at most one per slot.

No two markers may sit in neighbouring slots.

Return how many arrangements there are, modulo 10^9 + 7.

Examples

Example 1

Input
n = 9, k = 3
Output
35

Three markers over nine slots with none touching leaves seven slots to choose three positions from, which is 35 arrangements.

Example 2

Input
n = 3, k = 2
Output
1

The only arrangement puts markers in the first and last slots.

Example 3

Input
n = 2, k = 2
Output
0

Two markers cannot both fit in two neighbouring slots, so there is no arrangement.

Constraints

  • 1 <= n <= 5 * 10^5
  • 1 <= k <= n

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_valid_sequences(n: int, k: int) -> int:
Java
public int countValidSequences(int n, int k)

More on the same topics