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 și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T.

Cerința

Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1], A[2],...,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],...,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 ≤ N ≤ 15
• 2 ≤ T ≤ 1018
• 2 ≤ A[i] ≤ 50, 1 ≤ i ≤ N

Exemplu:

fibodiv.in

3 20
3 6 10

fibodiv.out

6

Explicație

N = 3; T = 20; A1 = 3, A2 = 6, A3 = 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, 1597, 2584, 4181, 6765. 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, 6765.