По данному натуральному 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.

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