성적
시간 제한1초메모리 제한512 MB
집합 A에 원소를 넣거나 빼는 질의가 끝날 때마다, A의 모든 원소를 0으로 채운 길이 P의 리스트에 배치하되 각 양수가 왼쪽의 가장 가까운 양수와 자기 값 이상 떨어지도록 하는 경우의 수를 1e9+7로 나눈 나머지로 구하고, 불가능하면 -1을 출력한다.
문제
AlekuKebap은 수학 시간에 있다. 1+1=2인 이유를 고민하는 동안, 선생님은 칠판에 조금 더 복잡한 문제를 쓰고 있었다. Q개의 질의와, 0으로 채워진 P개의 원소를 가진 리스트 S가 주어진다. 집합 A는 처음에 공집합이다. 질의는 다음과 같다.
0 x(집합 A에 값 x를 넣는다)1 x(집합 A에서 값 x를 지운다. 값 x가 집합 A에 존재함이 보장된다)
각 질의 후에도 A가 절대 비어 있지 않음이 보장된다. 매 질의가 끝난 뒤 선생님은 Aleku에게 다음을 묻는다. 집합 A의 모든 원소를 리스트 S에 (A의 순서대로일 필요는 없다) 배치해서 다음 조건을 만족하도록 할 수 있는가?
- 집합 A의 원소들은 서로 다른 위치에 놓이고, 나머지 위치는 0인 P개의 원소가 차지한다.
- S[i]를 S의 양수 원소, S[j]를 S[i] 왼쪽에 있는 가장 가까운 양수 원소라고 하면, i-j ≥ S[i]를 만족해야 한다.
- f를 S의 왼쪽에서 첫 번째 양수 원소라고 하면, f ≥ S[f]를 만족해야 한다.
이 질문의 답이 yes라면, 서로 다른 배치가 몇 개나 가능한지 구하라. 답이 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력하라. 답이 no라면 -1을 출력하라.
AlekuKebap이 선생님의 모든 질문에 올바르게 답해서 10점을 받도록 도와주자.
입력
첫 줄에 두 정수 Q와 P가 주어진다.
다음 Q개의 줄에 각 질의의 설명이 주어진다.
출력
Q개의 질문 각각에 대한 답을 한 줄에 하나씩 출력한다.
제한
- Q ≤ 100,000
- P ≤ 100,000
- 집합에 추가되는 모든 수는 ≤ 1,000,000이다.