407764: GYM102891 A Apples and Oranges

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?

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

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

• Subtask 1 (31 points): $$$n \le 10^6$$$
• Subtask 2 (23 points): $$$n \le 10^{12}$$$
• Subtask 3 (46 points): No additional constraints

0

1

2

6

9

20

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.