ICPC

타우키티아어 사전은 길이가 $N$ 이하인 모든 단어로 이루어져 있다. 단어는 영어 알파벳 소문자로 쓰인다. 지구의 사전과 달리 타우키티아어 사전은 단어를 먼저 길이 순으로, 그다음에 알파벳 순으로 정렬한다. 즉 한 글자 단어 'a'부터 'z'까지가 먼저 오고, 그다음 두 글자 단어 'aa'부터 'zz'까지가 오는 식이다.

앨리스는 타우키티아어의 모든 단어를 사전에 실린 순서대로 이어서 썼고, 긴 단어 하나를 얻었다. 이 단어에서 부분 문자열 <<icpc>>는 몇 번 나타나는가?

입력은 정수 $N$ ($1 \le N \le 10^9$) 하나를 포함한다. $N$은 타우키티아어 단어의 최대 길이이다.

부분 문자열 <<icpc>>가 나타나는 횟수를 $10^9+7$로 나눈 나머지를 출력한다.