Одиниці#10005
Розгляньмо всі можливі рядки довжини , що складаються з нулів і одиниць (усього таких рядків 2^n). Нас цікавлять ті з них, у яких є хоча б один відрізок з підряд ідучих одиниць. Завдання полягає в тому, щоб знайти кількість таких рядків. Оскільки це число може бути дуже великим, потрібно вивести залишок від ділення цього числа на .
Два натуральних числа і (1 \le n \le 100000, 1 \le k \le 100).
Виведіть залишок від ділення на кількості рядків, у яких є хоча б один відрізок з підряд ідучих одиниць.
Приклад 1
Приклад 2
Приклад 3