Phân đoạn
Cho dãy số $a_1,a_2,...,a_N$ và hai số $L$, $R$. Một cách phân đoạn dãy $a$ là cách chia dãy $a$ thành một hoặc một số đoạn, mỗi đoạn là một chuỗi các phần tử liên tục trong mảng $a$.
Đếm số cách phân đoạn dãy $a$ sao cho tổng của mỗi đoạn con nằm trong đoạn $[l, r]$.
Dữ liệu
- Dòng đầu tiên chứa ba số nguyên $N,L,R \ (1\le N\le 10^5; 1\le L\le R\le 10^{12})$;
- Dòng tiếp theo chứa $N$ số nguyên $a_i \ (1 \le a_i \le R)$.
Kết quả
- Kết quả bài toán sau khi chia lấy dư cho $10^9+7$.
Chấm điểm
30; $N\le 20$. 30; $N\le 10^3$. 40; Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
5 3 12
3 5 1 2 6
output
8
Giải thích
Các cách phân đoạn:
- (3)(5)(1 2 6)
- (3)(5 1)(2 6)
- (3)(5 1 2)(6)
- (3 5)(1 2)(6)
- (3 5)(1 2 6)
- (3 5 1)(2 6)
- (3 5 1 2)(6)
- (3)(5)(1 2)(6)
Comments