Problem E. Erasing numbers ≡

Statement

In the research institute where Timofey works, a successful study of the sequence of natural numbers is underway. Every day, his colleagues discover new and new properties of this sequence, and Timofey tries to keep up with them. Today, as usual, Timofey wrote down a row of natural numbers from 1 to n on the board and tries to answer the question of whether it is possible to erase several (at least one) consecutive numbers in the middle of the list so that the sum of the remaining numbers on the left is equal to the sum of the remaining numbers on the right.

Input format

The input consists of a single line containing a natural number n.

Output format

The output should include a non-negative integer, representing the number of different ways to erase numbers.

Constraints

3 ≤ n ≤ 10⁵

Explanations for examples

In the first example, n = 5. Let's list all the ways to erase numbers in the middle of the row:

• 1 # 3 4 5
• 1 2 # 4 5
• 1 2 3 # 5
• 1 # # 4 5
• 1 2 # # 5
• 1 # # # 5

In none of them does the required property hold.

In the second example, n = 21. Let's list all the good ways to erase numbers in the middle of the row:

• 1 2 3 4 5 6 # # # ## ## ## ## ## ## ## ## ## ## ## 21
• 1 2 3 4 5 6 7 8 9 10 11 12 ## ## ## ## ## 18 19 20 21

In the first list, the sum of the numbers on the left and right is 21, in the second — 78. There are two ways in total.

Sample tests

5

0

21

2