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.

Input

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

Output

• 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\).

Scoring

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

Example

5
2 5 3 1 2

5