ICPC

Time limit2sMemory limit512 MB

Summary

Concatenate all lowercase words of length 1 through N in length-then-alphabetical order; count occurrences of the substring "icpc" modulo 1e9+7, with N up to 1e9.

Level: Hard8 of 10
Topics: Combinatorics, String matching, Math, Dynamic programming
Solved: No attempts yet

Problem

The dictionary of the Tau Cetian language consists of all words whose length does not exceed $N$ . Words are written in lowercase letters of the English alphabet. In the Tau Cetian dictionary, unlike Earth dictionaries, words are ordered first by length and only then alphabetically. That is, one-letter words from 'a' to 'z' come first, then two-letter words from 'aa' to 'zz', and so on.

Alice wrote down all words of the Tau Cetian language in a row, in the order they appear in the dictionary, and obtained one long word. How many times does the substring <<icpc>> occur in this word?

Input

The input contains a single integer $N$ ( $1 \le N \le 10^9$ ), the maximum length of a word in the Tau Cetian language.

Output

Print one number: the remainder of dividing the number of occurrences of the substring <<icpc>> by $10^9+7$ .

Examples2

Example 1
Input
```
3
```
Expected output
```
0
```
Example 2
Input
```
5
```
Expected output
```
134
```