Quá chán nản với những bài toán đếm bộ \(3\) tam giác, bộ \(3\) số pythagore hay bộ \(3\) số giống nhau,… Đó đều là những bài toán tầm thường với mô típ và cách giải giống nhau. Nay Ami quyết định đếm bộ \(3\) số \(a, b, c\) có tính thứ tự sao cho \(a \mid b \mid c = n\). Kí hiệu | là phép toán thao tác bit OR. Tất nhiên đây cũng là bài toán cơ bản và cũ kĩ nhưng hi vọng với sự cách tân là phép OR, các bạn sẽ thấy bớt nhàm chán đi phần nào.

Input

• Một dòng duy nhất chứa số nguyên dương \(n\).

Output

• Một số nguyên duy nhất là kết quả bài toán.

Constraints

• \(n \le 10^6\).

Example

1

7