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

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

Вид клавиатуры телефона:

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Определите вероятность того, что сумма выпавших чисел будет в точности равна Q.