Dãy F-Fibonacci

Với hai số nguyên dương \(X, Y\) cho trước, dãy F-Fibonacci là dãy số được định nghĩa như sau:

• \(F_0 = X\); \(F_1 = Y\);

• \(F_i = F_{i-1} + F_{i-2}\) với mọi \(i \ge 2\).
  Cho dãy \(A\) gồm \(N\) số nguyên dương \(A_1, A_2, A_3, \ldots, A_N\). Người ta muốn chia dãy \(A\) thành các đoạn liên tiếp sao cho tổng các phần tử của mỗi đoạn con đều thuộc dãy F-Fibonacci.

Yêu cầu: Hãy đếm số cách chia dãy \(A\) thành các đoạn con sao cho tổng các phần tử của mỗi đoạn con đều thuộc dãy F-Fibonacci.

Input

Dữ liệu vào:

• Dòng đầu tiên gồm số nguyên dương \(N\) (\(1 \le N \le 10^5\));

• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) (\(1 \le A_i \le 10^9\));

• Dòng thứ ba gồm hai số nguyên \(X, Y\) (\(1 \le X \le Y \le 100\)).

Ràng buộc:

• Có \(40\%\) số test ứng với \(40\%\) số điểm có \(1 \le N \le 20\); \(1 \le A_i \le 10^5\);

• \(40\%\) số test khác ứng với \(40\%\) số điểm có \(1 \le N \le 1000\);

• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc thêm.

Output

In ra một số nguyên duy nhất là kết quả của bài toán sau khi chia dư cho \(10^9 + 7\).

Example

Input:

6
1 3 2 2 1 4
1 1

Output:

4

Note

Có \(4\) cách chia dãy số thỏa mãn như sau:

• \(\{1\}, \{3\}, \{2\}, \{2\}, \{1, 4\}\);

• \(\{1\}, \{3, 2\}, \{2\}, \{1, 4\}\);

• \(\{1, 3, 2, 2\}, \{1, 4\}\);

• \(\{1, 3, 2, 2, 1, 4\}\).