18103번 - ICPC 다국어

Словарь тау-китянского языка состоит из всех слов, длина которых не превосходит $N$. Слова записыаются строчными буквами английского алфавита. В тау-китянском словаре --- в отличие от земных --- слова сначала упорядочены по длине, а только затем по алфавиту, то есть сначала идут однобуквенные слова от 'a' до 'z', затем двухбуквенные --- от 'aa' до 'zz' и так далее.

Алиса выписала подряд все слова тау-китянского языка в том порядке, в котором они перечислены в словаре, и получила длинное слово. Сколько раз в этом слове встретится подстрока <<icpc>>?

Входные данные содержат одно целое число $N$ ($1 \le N \le 10^9$) --- максимальная длина слова в тау-китянском языке.

Вывелите одно число --- остаток от деления количества вхождений подстроки <<icpc>> на $10^9+7$.