Да, дела у Надиры с её автосалоном идут хорошо. Правда, у него до сих пор нет названия. Надира даже частично выкупила авторские права на букву 'a'. Теперь она может использовать эту букву, но не слишком часто: ей нельзя ставить буквы 'a' рядом друг с другом. Сколько разных допустимых вариантов названий есть у Надиры?
Одно целое число $$$N$$$ от 1 до $$$10^7$$$ — количество букв в планируемом названии автосалона.
Количество допустимых вариантов — строк длины $$$N$$$ из строчных латинских букв, не содержащих двух букв 'a' подряд. Поскольку ответ может оказаться очень большим, его следует вывести по модулю $$$10^9 + 7$$$.
2
675
2017
379347254
В первом примере допустимы все сочетания из двух букв, кроме «aa».
