Переформулюємо задачу мовою двійкових рядків. Кожному будинку відповідає символ: , якщо корова отримала банан, і інакше. Умова «не більше ніж корів із послідовними номерами можуть отримати банани» означає, що в рядку немає C+1 одиниці поспіль.
Отже, треба порахувати кількість двійкових рядків довжини без C+1 одиниць підряд.
Позначимо цю кількість через і виведемо рекурентність. Подивимось на початок рядка: нехай він починається з рівно одиниць, після яких іде нуль. Тут може бути від до , а решта рядка (довжини N - j - 1) — це будь-який допустимий рядок. Крім того, окремо можливий випадок, коли рядок складається з самих одиниць, — він допустимий лише при N \le C. Звідси при N > C
а база — f(n) = 2^n для 0 \le n \le C.
Перевіримо на прикладах з умови. Для C = 2 маємо f(0)=1, f(1)=2, f(2)=4, далі f(3) = 4+2+1 = 7 і f(4) = 7+4+2 = 13 — саме , як і сказано. Для C = 1: f(0)=1, f(1)=2, f(2)=3, f(3)=5 — знову збіг.
Якщо невелике, достатньо порахувати рекурентність напряму за або за , підтримуючи ковзну суму останніх C+1 значень (додаємо нове, віднімаємо те, що вийшло з вікна, — усе за модулем).
Якщо ж велике, скористайтеся тим, що це лінійна рекурентність сталого порядку C+1. Її можна обчислити за \mathcal{O}((C+1)^3 \log N) піднесенням матриці переходу до степеня або швидше — за \mathcal{O}((C+1)^2 \log N) методом Кітамаси (множенням многочленів за модулем характеристичного многочлена).
Не забувайте брати остачу за модулем 10^9 + 7 після кожного додавання; при відніманні у ковзній сумі додайте модуль, щоб не отримати від'ємне значення.