Cho một đa giác đều gồm \(n ~ (3 \leq n \leq {10}^9)\) đỉnh, các cạnh có độ dài là \(1\), các đỉnh được đánh số từ \(1\) đến \(n\) theo chiều ngược chiều kim đồng hồ. Một tam giác có thể được tạo thành từ \(3\) đỉnh \(i, j, k ~ (1 \leq i < j < k \leq n)\) phân biệt của đa giác. Tam giác có ba đỉnh \(i, j, k\) được kí hiệu là \(\triangle ijk\).

Hai tam giác \(\triangle ijk\) và \(\triangle i'j'k'\) được gọi là bằng nhau khi và chỉ khi các cạnh \(ij, jk, ik\) và \(i'j', j'k', i'k'\) có thể tạo thành \(3\) cặp cạnh, mỗi cặp có hai cạnh có độ dài bằng nhau, mỗi cạnh trong \(6\) cạnh kia thuộc đúng một cặp và mỗi cặp gồm một cạnh của \(\triangle ijk\) và một cạnh của \(\triangle i'j'k'\).

Trong trường hợp đầu tiên, tam giác \(\triangle 278\) bằng \(\triangle 356\) bởi vì

• cạnh 2-8 bằng cạnh 3-5,
• cạnh 2-7 bằng cạnh 3-6,
• cạnh 5-6 bằng cạnh 7-8.

Trong trường hợp thứ hai, hai tam giác đã cho bằng nhau.

Trong trường hợp thứ ba, hai tam giác đã cho không bằng nhau.

Yêu cầu: hãy đưa ra số tam giác phân biệt trong tất cả các tam giác có thể tạo từ \(n\) đỉnh của đa giác.

Input

• Dòng đầu tiên chứa duy nhất một số nguyên dương \(n\).

Output

• Chứa một số nguyên duy nhất là số tam giác phân biệt.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 1000\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq {10}^5\).
• Subtask \(4\) (\(40\%\) số điểm): \(n \leq {10}^9\).

Example

3

1

10

8

20

33