경곽이는 며칠 전까지 분자 검출기를 만드는 회사에 다니고 있었다. 각각의 분자들은 양의 정수인 무게를 가지고 있다. 분자 검출기는 검출 범위 [l, u]를 가지고 있고, l과 u는 각각 양의 정수이다. 분자 검출기는 포함하는 분자들의 전체 무게가 검출 범위 내부에 있는 분자들의 집합만 검출할 수 있다. 엄밀하게, w_1, ... w_n의 무게를 가지고 있는 n개의 분자가 있다고 하자. n개 분자의 부분집합 중 l <= w_i1 + ... + w_im <= u를 만족하는 서로 다른 인덱스의 집합 I = {i1, ..., im}이 존재할 때, 이 부분집합에 대하여 검출은 성공이다. 경곽이의 일은 어떤 분자들의 집합이 주어졌을 때 검출을 성공시키는 부분 집합의 개수를 구하는 것이다. 그런데, 실제로는 경곽이에게 분자를 조달하는 분자 생산팀에서 집합에 넣어야 하는 분자를 빠뜨리거나 빼야 하는 분자를 넣는 등 실수를 거듭하여 경곽이에게 뒤늦게 보고하는 일이 빈번하게 발생하였고, 그 때마다 경곽이는 결과를 새로 산출해야 했다. 경곽이는 모든 계산을 수작업으로 진행했기 때문에, 보통 해야 할 일이 경곽이의 근무 시간 안에 끝나지는 않았다. 경곽이는 거듭되는 야근에도 쥐꼬리만한 봉급밖에 받지 못하는 자신의 열악한 근무 환경에 분노를 느껴 며칠 전 회사를 떠났다. 경곽이의 후임인 당신은 이를 반면교사로 삼아 당신의 일을 대신하는 프로그램을 작성하여 일을 대신 시키고 당신은 회사에서 스도쿠를 즐기려는 계획을 세웠다. 그 원대한 계획을 실행하기 위해서, 당신은 다음과 같은 일을 처리하는 프로그램을 작성해야 한다. - 초기에 N(1<=N<=2,000)개의 분자가 존재하며, 각각의 무게는 2,000 이하의 양의 정수이다. 분자의 번호는 입력으로 주어지는 순서대로 1~N이다. - l과 u는 각각 2,000 이하의 양의 정수이다. - 당신의 프로그램은 다음의 질의를 합쳐서 Q(1<=Q<=4,000)번 처리해야 한다. - 질의 1 : 무게가 W(1<=W<=2,000)인 새로운 분자를 집합에 추가한다. i번째로 새로 추가된 분자의 인덱스는 N+i이다. - 질의 2 : 인덱스가 i인 분자를 집합에서 제거한다. 이미 제거된 분자라면 아무 일도 일어나지 않는다. - 질의 3 : 현재의 분자 집합에서 검출을 성공시키는 부분 집합의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

분자 검출

문제 설명

입력

출력

예제

코드 제출

로그인

LOGIN