D. Different Triangles
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the quiet hours of a long evening, you find yourself with a box of matchsticks and a growing curiosity. With these simple sticks, you begin constructing triangles, starting with a classic 3-4-5 triangle. After counting 12 matchsticks to form this first shape, a question sparks in your mind: How many distinct triangles can be formed using at most $$$N$$$ matchsticks? Each side of these triangles must be made up of an integer number of matchsticks, and the triangles must have a positive area.

To add to the complexity, triangles that are merely rotations or reflections of each other are considered the same. For example, triangles with sides 3-4-5, 4-5-3, and 5-3-4 are indistinguishable under these rules.

Because this number can be very large print it modulo $$$10^9 + 7$$$

Input

A single integer $$$N$$$ $$$(1 \leq N \leq 10^6)$$$ representing the total matchsticks available

Output

Output a line with a single integer number, the number of distinct triangles that can be formed using at most $$$N$$$ matchsticks modulo $$$10^9 + 7$$$.

Examples
Input
5
Output
2
Input
12
Output
18