5275 : A76 - 강 건너기
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
강폭이 $W$ 미터인 KYOPRO 강에는 $N$ 개의 발판이 일직선상에 놓여 있으며, 서쪽부터 순서대로 1부터 $N$ 까지 번호가 붙어 있습니다. 발판 $i \ (1 \leq i \leq N) $ 는 서쪽 강둑에서 $X_i$ 미터 지점에 있습니다.
타로 군은 동쪽 방향으로 점프를 반복하여 서쪽 강둑에서 동쪽 강둑까지 이동하려고 합니다. 하지만 한 번의 점프로 날아가는 거리는 너무 길거나 짧으면 안 되며, $L$ 미터 이상 $R$ 미터 이하여야 합니다. 이동 방법은 총 몇 가지입니까?
[제약 조건]
• $1 \le N \le 150{,}000$
• $0 < X_1 < X_2 < \cdots < X_N < W \le 10^{9}$
• $1 \le L \le R \le W$
타로 군은 동쪽 방향으로 점프를 반복하여 서쪽 강둑에서 동쪽 강둑까지 이동하려고 합니다. 하지만 한 번의 점프로 날아가는 거리는 너무 길거나 짧으면 안 되며, $L$ 미터 이상 $R$ 미터 이하여야 합니다. 이동 방법은 총 몇 가지입니까?
[제약 조건]
• $1 \le N \le 150{,}000$
• $0 < X_1 < X_2 < \cdots < X_N < W \le 10^{9}$
• $1 \le L \le R \le W$
입력 설명
첫째 줄에 $N, W, L, R$ 이 주어집니다.
둘째 줄에 발판의 위치 $X_1, \ldots, X_N$ 이 주어집니다.
둘째 줄에 발판의 위치 $X_1, \ldots, X_N$ 이 주어집니다.
출력 설명
이동 방법의 가짓수를 1,000,000,007로 나눈 나머지를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 65 7 37
5 15 30 50 55
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7