A. Apples and Oranges
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

It is lunch time in Kiyosumi High School. As usual, the principal prepared apples and oranges for everyone. There are $$$k$$$ students in the school, and each of them has at most 1 apple and at most 1 orange.

A pair of people can share their food with each other, if and only if the total count of their apples and their oranges are both even. The principal has told you that:

  • There are $$$n$$$ pair of students that can share their food with each other.
  • Suppose that you have $$$a$$$ apples and $$$o$$$ oranges, where $$$a$$$ and $$$o$$$ are nonnegative integers. Then there is at least one student that you can share food with.

The $$$i$$$-th student has $$$a_i$$$ apples and $$$o_i$$$ oranges. Consider the multiset $$$S$$$ of pairs defined as $$$S = \{(a_1, o_1), (a_2, o_2), \dots, (a_k, o_k)\}$$$. Given $$$n$$$ and that what the principal said is true, how many different multisets can be constructed this way?

Input

The input contains an integer $$$n$$$ ($$$0 \le n \le 10^{18}$$$).

Output

Print one integer, the number of different multisets that can be constructed.

Scoring
  • Subtask 1 (31 points): $$$n \le 10^6$$$
  • Subtask 2 (23 points): $$$n \le 10^{12}$$$
  • Subtask 3 (46 points): No additional constraints
Examples
Input
0
Output
1
Input
2
Output
6
Input
9
Output
20
Note

In example 1, the only possible multiset is $$$\{(0, 0),(0, 1),(1, 0),(1, 1)\}$$$.

In example 2, $$$\{(0, 1),(1, 1),(0, 1),(0, 0),(1, 1),(1, 0)\}$$$ is a possible multiset.