가희와 전기 요금 2

시간 제한1초메모리 제한512 MB

요약
96원/kWh 요율로 각 컴퓨터의 전력량을 계산했을 때 총요금이 c1원 이상 c2원 이하가 되는 부분집합의 수를 10^9+7로 나눈 나머지를 구한다.
난이도

보통10점 중 7점

유형
조합론, 동적 계획법, 수학, 정렬
정답자
아직 제출이 없습니다

문제

가희는 집에 있는 nn대의 컴퓨터 중 몇 대의 컴퓨터를 사용하였습니다. 그런데 이번 달에 어떤 컴퓨터들을 사용했는지 모릅니다. 가희는 여러분들에게 아래 정보들을 알려주었습니다.

  • 이번 달에 청구된 요금은 c_1c\_{1}원 이상 c_2c\_{2}원 이하입니다.
  • 요율은 9696원/kWhkWh입니다.
  • 가희는 컴퓨터 외 전력을 소비하는 다른 제품을 사용하지 않았습니다.

최소한 11개 이상의 컴퓨터를 사용한 상태가 다르다면 다른 경우로 셉니다. 이때, 가희가 컴퓨터를 사용한 상태의 가짓수는 몇 가지일까요?

입력

첫 번째 줄에 가희 집에 있는 컴퓨터의 개수 nn이 주어집니다.

다음 nn개의 줄에 걸쳐 aa와 mm이 공백으로 구분되어 주어집니다. 이는 소비 전력이 aWaW인 컴퓨터를 mm분 동안 사용하였음을 의미합니다.

마지막 줄에 c_1c\_{1}과 c_2c\_{2}가 공백으로 구분되어 주어집니다.

출력

문제의 정답을 109+710^{9} + 7로 나눈 나머지를 출력해 주세요.

제한

  • 1≤n≤2001 ≤ n ≤ 200
  • 1≤a≤1091 ≤ a ≤ 10^{9}
  • 1≤m≤446401 ≤ m ≤ 44640
  • 1≤c_1≤c_2≤300,0001 ≤ c\_{1} ≤ c\_{2} ≤ 300\\,000
  • aa는 250250의 배수이고, mm은 1515의 배수입니다.

예제2

  1. 예제 1

    입력
    2
    1000 60
    1000 60
    96 96
    
    예상 출력
    2
    
  2. 예제 2

    입력
    3
    250 15
    500 30
    250 60
    12 96
    
    예상 출력
    6