fibofrac

Fie șirul Fibonacci dat prin $F_1$ = 1, $F_2$ = 1 și relația de recurență $F_k = F_{k-1} + F_{k-2}, \ k ≥ 3$. Se consideră un număr natural $N$.

Cerința

Să se scrie un program care determină numărul $F$ al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii $N$ termeni ai șirului $Fibonacci$.

Date de intrare

Fişierul de intrare fibofrac.in conţine pe prima linie numărul $N$.

Date de ieșire

Fişierul de ieşire fibofrac.out va conţine pe prima linie numărul $F$,cu semnificația de mai sus.

Restricții și precizări

• $1 \leq N < 1 \ 000 \ 000$;
• $0 \le F < 2^{63}$;
• Două fracții ireductibile $\frac{a}{b}$ și $\frac{c}{d}$ sunt diferite dacă $a \ne c$ sau $b \ne d$;
• Pentru teste în valoare de $24$ puncte, $1 \leq N < 80$;
• Pentru teste în valoare de $40$ puncte, $1 \leq N \leq 1 \ 100$;
• Pentru teste în valoare de $56$ puncte, $1 \leq N \leq 50 \ 000$.

Exemplul 1

fibofrac.in

7

fibofrac.out

14

Explicație

$N=7$; Primii $7$ termeni ai șirului Fibonacci sunt: $1, 1, 2, 3, 5, 8, 13$

Se pot forma $14$ fracții diferite ireductibile subunitare: $\frac{1}{2}$, $\frac{1}{3}$, $\frac{1}{5}$, $\frac{1}{8}$, $\frac{1}{13}$, $\frac{2}{3}$, $\frac{2}{5}$, $\frac{2}{13}$, $\frac{3}{5}$, $\frac{3}{8}$, $\frac{3}{13}$, $\frac{5}{8}$, $\frac{5}{13}$, $\frac{8}{13}$

Exemplul 2

fibofrac.in

2019

fibofrac.out

1547722

Explicație

Se pot forma $1547722$ de fracții diferite ireductibile subunitare utilizând primii $2019$ termeni ai șirului Fibonacci.

Exemplul 3

fibofrac.in

500000

fibofrac.out

94988288219

Explicație

Se pot forma $94988288219$ de fracții diferite ireductibile subunitare utilizând primii $500000$ termeni ai șirului Fibonacci.