Hôm nay bin9638, ông trùm của tổ chức “Code ver 4.0” tổ chức 1 cuộc lọc thành viên. Để có thể ở lại tổ chức các thành viên phải giải 1 bài toán do ông trùm đưa ra. Bài toán là cho 1 số tự nhiên \(N (N\leq 10^{18})\), các thành viên phải đưa ra số tam giác có 3 cạnh nguyên sao cho \(N\) là cạnh lớn nhất của tam giác (lớn nhất ở đây là lớn hơn hẳn). Rose là \(1\) thành viên mới của tổ chức, khổ nỗi do cô vừa mới đi làm MV "How that like you" nên đã quên hết kiến thức, vì rất sự bị loại nên cô muốn nhờ bạn giúp. Nếu giúp được cô ấy thì bạn sẽ được thưởng một nụ hôn đấy !

Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho \(10^9+7\)

Yêu cầu: hãy đếm số tam giác thỏa mãn đề bài.

Input

• 1 dòng duy nhất là số \(N\).

Output

• 1 dòng duy nhất là kết quả.

Scoring

• Subtask #1 (\(40\%\) số điểm): \(N \leq 10^7\).
• Subtask #2 (\(60\%\) số điểm): \(N \leq 10^{18}\).

Example

3

1

4

2