Problem Statement

Binary Strings with No K Consecutive Ones Given N and K , count binary strings of length N that satisfy both conditions: the string contains no substring of K consecutive 1 bits; its first bit and last bit are different. Print the count modulo 1000000007 . Input The first line contains N . The second line contains K . Output Print the number of valid strings modulo 1000000007 . Constraints 1 <= N <= 100000 1 <= K <= N Examples Input: 3 2 Output: 2 The valid strings are 001 and 100 . Input: 4 3 Output: 6 The valid strings are 0001 , 0011 , 0101 , 1000 , 1010 , and 1100 . Notes For N=1 , the answer is 0 because the first and last bit are the same position. For K=1 , no 1 is allowed, so the answer is also 0.