OMG和SSY的故事

Time Limit: 1000ms

Memory Limit: 65536KB

Description

  由于某种原因,RSL被未知的势力抓走了!
  SSY为了救回RSL,穿越时空遇到了奸商OMG,出人意料的OMG看上了SSY,被派人采取粗暴的方式留下来SSY,但是长久以来,SSY一直不肯答应OMG,所以OMG决定给SSY一个机会,如果他答出了这个问题,就放他走。
  问题如下描述:OMG手里有一批鸡想要出售,作为偏执狂,他想要卖出的鸡的价格为不同的斐波那契数,且总和为n。他想要知道有多少种方案能够满足。(如果SSY不能解决,那么就要和OMG共度余生,(其实SSY的内心早已有了OMG, 滑稽))

Input

  输入一个数n(1<=n<=1e18)

Output

  输出方案数

Sample Input

2
16

Sample Output

1
4

Hint

None

Source

None

提交代码