По данным натуральным n и k определите количество последовательностей длины n из 0 и 1, не содержащих k одинаковых символов подряд. n≤10⁶, 2≤k≤n+1. Гарантируется, что ответ не превосходит 2³¹-1.