From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more than $K$.
For $N \le 2\times 10^6$, my approach is to using DP. dp[N][K][2]
is the number of ways to fill string of length $N$ with the current $1$'s consecutive sequence length is $K$ and last parameter is to tell whether the current string contains the $1$'s consective sequence of length $K$.
This would work if N is small enough but the constraints of this problem is : $1 \le N \le 10^{10}, 0 \le K \le 50$.
The approach I need is obviously Matrix Exponentiation so I can solve it in $O(\log N \times ?)$. Storing every possible binary strings of length K is not possible ($2^M$). Can anyone provide the solution of the problem? Or at least some hints