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.

Dữ liệu vào:

+ 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})\).

Kết quả:

+ Ghi một số duy nhất là phần dư của số cách chia sau khi chia cho \((10^{9}\ + \ 7)\).

Ví dụ:

Input	Output
5 2 5 3 1 2	5

Giải thích : Có 5 cách chia là:

• \(\lbrack 2\rbrack,\ \lbrack 5\rbrack,\ \lbrack 3\rbrack,\ \lbrack 1\rbrack,\ \lbrack 2\rbrack\)

• \(\lbrack 2\rbrack,\ \lbrack 5\rbrack,\ \lbrack 3\rbrack,\ \lbrack 1,\ 2\rbrack\)

• \(\lbrack 2\rbrack,\ \lbrack 5,\ 3\rbrack,\ \lbrack 1\rbrack,\ \lbrack 2\rbrack\)

• \(\lbrack 2\rbrack,\ \lbrack 5,\ 3\rbrack,\ \lbrack 1,\ 2\rbrack\)

• \(\lbrack 2,\ 5,\ 3,\ 1,\ 2\rbrack\)

Ràng buộc:

+ Subtask 1: Có 30% test có \(n \leq \ 10\).

+ Subtask 2: Có 30% số test khác có \(n \leq \ 10^{3}\).

+ Subtask 3: Có 40% số test còn lại không có ràng buộc gì thêm.