Dãy Fibonacci

Cho dãy $a$ gồm $n$ phần tử được đánh chỉ số từ $1$ đến $n$. Hãy đếm số cách chia dãy $a$ thành các dãy con gồm các phần tử liên tiếp sao cho tổng của mỗi dãy con là một số Fibonacci.

Mỗi phần tử thuộc đúng một dãy con. Hai cách chia được coi là khác nhau nếu tập các vị trí cắt khác nhau. Dãy Fibonacci được xác định bởi $F_1=F_2=1$, $F_k=F_{k-1}+F_{k-2}$ với $k\ge 3$, nên các số Fibonacci là $1,2,3,5,8,13,\dots$

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ $(1\le n\le {10}^5)$;
• Dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ $(1\le a_i\le {10}^9)$.

Dữ liệu ra

Một dòng duy nhất chứa một số nguyên là phần dư của số cách chia sau khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le {10}^9$

Subtasks

• Subtask 1 ($30\%$ số điểm): $n\le 10$.
• Subtask 2 ($30\%$ số điểm): $n\le {10}^3$.
• Subtask 3 ($40\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ