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

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

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

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

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