문제
관영이의 취미는 장난감 저울을 가지고 노는 것이다. 관영이에겐 장난감 양팔 저울과 N종류의 무게추가 있다. 무게추는 서로 다르게 생겼기 때문에, 같은 무게의 무게추라도 서로 다르다. 각 종류마다 무게추는 무한히 있다고 가정한다.
관영이는 다 큰 고등학생이기 때문에, 그냥 무게추를 가지고 노는 것은 싫증이 나 버렸다. 그래서 관영이는 고등학생답게 함수 F(X)를 정의하고 그것을 더하며 놀기 시작했다. F(X)는 무게 X를 여러가지 추를 이용하여 재는 서로 다른 방법의 수이다. 예를 들어, 무게추가 1g, 1g, 2g 세 종류가 있다면, F(2) = 4가 된다. 두 1g 추가 서로 다르다는 점에 유의해서 다음을 보면 알 수 있다:
1g(1번 추)를 두개 쓴다.
1g(2번 추)를 두개 쓴다.
1g(1번 추)와 1g(2번 추)를 쓴다.
2g 추를 쓴다.
N개의 추의 무게와, L, R이 주어졌을 때, F(L)+F(L+1)+….+F(R)을 구하는 프로그램을 작성하라.
[부분문제의 제약 조건]
부분문제 1: 전체 점수 100점 중 42점에 해당하며 1 <= L <= R <= 105이다.
부분문제 2: 전체 점수 100점 중 58점에 해당하며, 원래의 제약조건 이외에 아무 제약조건이 없다.
입력
표준 입력으로 다음 정보가 주어진다.
첫 줄에 정수 N이 주어진다. N은 무게추 종류의 수이다.
둘째 줄에, N개의 각 종류의 무게추들의 무게가 공백을 사이에 두고 주어진다.
셋째 줄에, L과 R이 공백을 사이에 두고 주어진다. (1 <= N <= 10, 0 < 무게추들의 각 무게 <= 105, 1 <= L <= R <= 1017) 무게추들의 무게의 곱 <=105이다.
출력
F(L) + F(L+1) + …. + F(R)을 109+7로 나눈 나머지를 출력한다.
예제
3
1 2 3
1 6
22
로그인해야 코드를 작성할 수 있어요.