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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
bin9638
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, Perl, PHP, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, Scratch, Swift
Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 
3
Output 
1
Note

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

Test 2

Input 
4
Output 
2
Note

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

Bình luận


  • 0
    todonghai2k7    3:30 p.m. 25 Tháng 8, 2020

    Bài này ko nên cho ngôn ngữ python :)))))


    • -12
      N7hoatt    3:44 p.m. 25 Tháng 8, 2020 ← đã chỉnh sửa

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

      4 bình luận nữa