{"code":"cnttriangle2","name":"Đếm Tam Giác (Bản Khó)","description":"Hôm nay [user: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 !\r\n\r\nVì kết quả có thể rất lớn nên hãy in ra **phần dư** khi chia cho $10^9+7$\r\n\r\n\r\n**Yêu cầu:** hãy đếm số tam giác thỏa mãn đề bài.\r\n\r\n#### Input\r\n\r\n- 1 dòng duy nhất là số $N$.\r\n\r\n#### Output\r\n\r\n- 1 dòng duy nhất là kết quả.\r\n\r\n#### Scoring\r\n\r\n - Subtask #1 ($40\\%$ số điểm): $N \\leq 10^7$.\r\n - Subtask #2 ($60\\%$ số điểm): $N \\leq 10^{18}$.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        3\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        1\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n\r\n        Ví dụ $1$ có $1$ tam giác duy nhất là $[2,2,3]$.\r\n\r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        4\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        2\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n\r\n        Ví dụ $2$ có $2$ tam giác là $[2,3,4]$ và $[3,3,4]$.","points":300.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}