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