Problem Description

Nishimori decided to call a triangle that satisfies the following three conditions a "pseudo-isosceles triangle":

• All sides have integer lengths.
• All sides have different lengths.
• The difference between the lengths of any two sides is 1.

Calculate the number of pseudo-isosceles triangles whose perimeter is less than or equal to \( L \), and output the result modulo \( 1000000007 \).

Input Format

The input is given from the standard input in the following format:

\( L \)

• The maximum perimeter \( L \) (\( 5 \leq L \leq 10^{12} \)) is given in one line.

Output Format

Calculate the number of pseudo-isosceles triangles whose perimeter is less than or equal to \( L \), and output the result modulo \( 1000000007 \). Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

10

Sample Output #1

1

Sample Input #2

1100011

Sample Output #2

251098945

Notes/Hints

Scoring

This problem has partial scoring:

• If you correctly solve all test cases where \( L \leq 10^6 \), you will be awarded 25 points.
• If you correctly solve all test cases, you will be awarded an additional 75 points.

见题面 Input 部分

见题面 Output 部分