Đếm Tam Giác (Bản Khó)

Author:

Problem types

Allowed languages

~~Assembly~~, Awk, C, C#, C++, Clang, Clang++, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, Scratch, ~~Swift~~

Points: 300 Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

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

Test 1

Input

Output

Note

Ví dụ \(1\) có \(1\) tam giác duy nhất là \([2,2,3]\).

Test 2

Input

Output

Note

Ví dụ \(2\) có \(2\) tam giác là \([2,3,4]\) và \([3,3,4]\).

Comments (9)

Order by

Loading comments...