Given n and k where
0 <= n <= 10^5 and
1 <= k <= min(n, 10^5) and k is even
A nice string of length n is a binary string such that for all substrings of length k, number of 1s equal number of 0s.
let c_i equal number of 1s in the i_th valid string — (k/2)
Compute summation ( 2 ^ c_i ) for all nice strings, modulo 1000000007.
example n=6, k=4
one nice string is 001100 -> c_i = 2 — 2 = 0 -> 2^c_i = 1
another nice string is 101010 -> c_i = number of 1s — k/2 = 3 — 2 = 1 -> 2^c_i = 2
yet another example is 110011 -> c_i = number of 1s — k/2 = 4 — 2 = 2 -> 2^c_i = 4
010101-> 1
101010 -> 1
011001-> 1
100110 > 1
ans = (1+2+4+1+1+1+1) % 1000000007 = 11