가희와 전기 요금 2
시간 제한1초메모리 제한512 MB
96원/kWh 요율로 각 컴퓨터의 전력량을 계산했을 때 총요금이 c1원 이상 c2원 이하가 되는 부분집합의 수를 10^9+7로 나눈 나머지를 구한다.
문제
가희는 집에 있는 대의 컴퓨터 중 몇 대의 컴퓨터를 사용하였습니다. 그런데 이번 달에 어떤 컴퓨터들을 사용했는지 모릅니다. 가희는 여러분들에게 아래 정보들을 알려주었습니다.
- 이번 달에 청구된 요금은 원 이상 원 이하입니다.
- 요율은 원/입니다.
- 가희는 컴퓨터 외 전력을 소비하는 다른 제품을 사용하지 않았습니다.
최소한 개 이상의 컴퓨터를 사용한 상태가 다르다면 다른 경우로 셉니다. 이때, 가희가 컴퓨터를 사용한 상태의 가짓수는 몇 가지일까요?
입력
첫 번째 줄에 가희 집에 있는 컴퓨터의 개수 이 주어집니다.
다음 개의 줄에 걸쳐 와 이 공백으로 구분되어 주어집니다. 이는 소비 전력이 인 컴퓨터를 분 동안 사용하였음을 의미합니다.
마지막 줄에 과 가 공백으로 구분되어 주어집니다.
출력
문제의 정답을 로 나눈 나머지를 출력해 주세요.
제한
- 는 의 배수이고, 은 의 배수입니다.