Phân đoạn giới hạn (Bounded Segmentation)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $A_1,A_2,\ldots,A_N$ và hai số nguyên $L,R$ với $L\le R$. Cần chia toàn bộ dãy thành một số đoạn liên tiếp không rỗng. Một đoạn được gọi là hợp lệ nếu tổng các phần tử của đoạn thuộc $[L,R]$.

Hãy đếm số cách chia toàn bộ dãy thành các đoạn hợp lệ. Hai cách chia khác nhau nếu có ít nhất một vị trí đặt dấu cắt khác nhau. Kết quả lấy modulo $10^9+7$.

Input

• Dòng đầu chứa ba số nguyên $N,L,R$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In một số nguyên duy nhất là số cách chia theo modulo $10^9+7$.

Subtask

• Subtask 1 (25%): $1\le N\le 25$, $-10^14\le L\le R\le 10^14$, $|A_i|\le 10^9$.
• Subtask 2 (30%): $1\le N\le 2000$, $-10^14\le L\le R\le 10^14$, $|A_i|\le 10^9$.
• Subtask 3 (45%): $1\le N\le 2\cdot 10^5$, $-10^14\le L\le R\le 10^14$, $|A_i|\le 10^9$.

Ví dụ

Ví dụ 1

Input

5 2 3
1 1 1 1 1

Output

2

Giải thích

Có hai cách chia theo độ dài các đoạn: $2+3$ và $3+2$. Mỗi đoạn khi đó có tổng bằng $2$ hoặc $3$.

Ví dụ 2

Input

3 0 0
1 -1 0

Output

2

Giải thích

Hai cách hợp lệ là $[1,-1]\,[0]$ và $[1,-1,0]$.