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.

Biết rằng dãy số Fibonacci ~\{F_n\}~ là một dãy số nguyên được xác định bởi quan hệ truy hồi ~F_n = F_{n-1} + F_{n-2}~ với điều kiện ban đầu ~F_0 = 0~, ~F_1 = 1~. Một số phần tử đầu tiên của dãy Fibonacci là ~0, 1, 1, 2, 3, 5, 8, \dots~

Input

• 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~ ~(0 \le A_i \le 10^9; 1 \le i \le N)~ biểu thị dãy số ~A~, các số cách nhau bởi dấu cách.

Output

Ghi 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~.

Scoring

Sample Input 1

5
2 5 3 1 2

Sample Output 1

5

Notes

Có ~5~ cách chia là:

• ~[2], [5], [3], [1], [2]~;

• ~[2], [5], [3], [1, 2]~;

• ~[2], [5, 3], [1], [2]~;

• ~[2], [5, 3], [1, 2]~;

• ~[2, 5, 3, 1, 2]~.