Sum of Fibonacci Numbers (Easy)

2 secs 1024 MB
magurofly's icon magurofly

問題文

フィボナッチ数列は 0,1,1,2,0, 1, 1, 2, \ldots という無限に続く数列で、

F0=0F1=1Fn=Fn2+Fn1(n2)\begin{aligned} F_0 &= 0 \\ F_1 &= 1 \\ F_n &= F_{n - 2} + F_{n - 1} & (n \ge 2) \end{aligned}

と表されます。

ところで、非負整数 NN に対し、 N=Fi+FjN = F_i + F_j となるような非負整数の組 (i,j)(i, j) はいくつ存在しますか?

制約

  • 0N10180 \le N \le 10^{18}
  • 入力はすべて整数である

入力

NN

出力

答えを 11 行に出力せよ。

入出力例

入力例1
3
出力例1
6

(0,4),(1,3),(2,3),(3,2),(3,1),(4,0)(0, 4), (1, 3), (2, 3), (3, 2), (3, 1), (4, 0) が存在します。

入力例2
12
出力例2
0

存在しないこともあります。

提出


Go (1.21)