Product Representation by Fibonacci Numbers

Given a natural number n, count the number of ways to represent it as a product of one or more Fibonacci numbers that are greater than 1. Only Fibonacci numbers greater than 1 (i.e. 2, 3, 5, 8, 13, …) can be used as factors.

Note that the order of the factors does not matter (i.e. 2 * 3 is considered the same as 3 * 2), so each combination should be counted once.

A valid representation is a sequence of Fibonacci numbers (in non-decreasing order) whose product equals n.

The Fibonacci sequence here is defined as:
\(F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, \dots\) .

Since 1 is not greater than 1, only Fibonacci numbers \(\geq 2\) are allowed.

inputFormat

The input consists of a single line containing a natural number n (\(n \ge 2\)).

It is guaranteed that n is such that the number of representations is computable within time limits.

outputFormat

Output a single number representing the number of ways to represent n as a product of one or more Fibonacci numbers (with each Fibonacci number being greater than 1).

sample

2

1