Count Binary Strings

Definitions - For a string S consisting of characters S1, S2, ..., SN, S[i, j] denotes the substring of characters Si, Si + 1, ..., Sj. - LCP(S1, S2) is defined as the length of the longest common prefix of strings S1 and S2. Problem Given positive integers N, K and M, count how many binary strings S of length N exist such that there exist more than M indices i such that LCP(S[1, i], S[i + 1,