You are given two integers N and K.
You need to count the number of binary strings of length N such that:
- The string does not contain K consecutive 1s.
- The first and last characters of the string are different.
Find the number of valid strings modulo 10^9 + 7.
4 2
4
Valid strings of length 4 with no 2 consecutive 1s where first and last characters differ:
- '0001'
- '0101'
- '1000'
- '1010'
Total = 4 strings.
4 3
6
For N = 4 and K = 3 (no '111'):
Starting with '0' and ending with '1': '0001', '0011', '0101' (3 strings).
By symmetry, starting with '1' and ending with '0': '1000', '1100', '1010' (3 strings).
Total = 3 + 3 = 6.
1. If N < 2 or K <= 1, no string can have different first and last characters without violating constraints, return 0. 2. By symmetry under string reversal, Count(Starts with 0, Ends with 1) == Count(Starts with 1, Ends with 0). 3. Answer = 2 * Count(Starts with 0, Ends with 1) % MOD. 4. To count strings of length N starting with '0' and ending with '1' with no K consecutive 1s: - Let dp[j] be the number of ways ending with j consecutive 1s (0 <= j < K). - Initially at length 1 (string is '0'): dp[0] = 1, all other dp[j] = 0. - For each step from length 2 to N: next_dp[0] = sum(dp[0..K-1]) % MOD next_dp[j] = dp[j-1] for j from 1 to K-1. - At length N, string must end with '1', so sum dp[1..K-1]. - Can be maintained in O(N) using sliding window sum for next_dp[0].