시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

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

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

입력

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

출력

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

예제 입력 1

3

예제 출력 1

0

예제 입력 2

5

예제 출력 2

134