fibodiv

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 \geq 3$. Se consideră un număr natural $N$ și un șir $A_1$, $A_2$, $\dots$, $A_N$ de $N$ numere naturale distincte. Se consideră de asemenea şi un număr natural $T$.

Cerință

Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci $F_1$, $F_2$, $\dots$, $F_T$ care sunt divizibili cu cel puțin unul dintre numerele $A_1$, $A_2$, $\dots$, $A_N$.

Date de intrare

Fişierul de intrare fibodiv.in conţine pe prima linie numerele $N$ și $T$ separate printr-un spațiu, iar pe a doua linie $N$ numere naturale, $A_1$, $A_2$, $\dots$, $A_N$, separate prin câte un spațiu.

Date de ieșire

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

Restricții și precizări

• $1 \leq N \leq 15$
• $2 \leq T \leq 10^{18}$
• $2 \leq A_i \leq 50$, $1 \leq i \leq N$

Exemplu

fibodiv.in

3 20
3 6 10

fibodiv.out

6

Explicație

$N = 3$; $T = 20$; $A_1$ = $3$, $A_2$ = $6$, $A_3$ = $10$

Primii $20$ de termeni ai șirului Fibonacci sunt: $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, $89$, $144$, $233$, $377$, $610$, $987$, $1 \ 597$, $2 \ 584$, $4 \ 181$, $6 \ 765$. Printre aceștia se găsesc 6 termeni divizibili cu cel puțin unul dintre numerele $3$, $6$, $10$ și anume: $3$, $21$, $144$, $610$, $987$, $6 \ 765$.