404992: GYM101727 D Interview Task

Alexey is a very experienced interviewer. Though he had done several hundreds of internship interviews, he feels that it is time to change something. The candidates now easily solve all the wonderful tasks he was successfully using for all these years.

There is no choice, so Alexey came up with a new task. You are given a sequence of integers that on step one consists of two integers 1. On each step you insert a new element between any two neighboring elements of a sequence, and a value of a new element is equal to their sum. After several first steps the sequence looks like as follows:

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

During the interview Alexey plans to ask candidate to write a program that, being given an integer value n, will compute the number of time value n occurs in the sequence on step n. Though Alexey has no idea how to solve this problem, he heard that the next candidate is an experienced participant of programming competition, so he should be able to come up with a solution.

The input consists of a single integer n (1 ≤ n ≤ 10¹³).

Print one integer, the number of times integer n appears in the sequence on step n.

4

2

1

2