밭과 농부

농사는 힘든 일이며, 땅을 사는 것은 그 시작일 뿐이다. 전체 농경지는 단위 정사각형 밭(field) 들로 이루어진 거대한 직사각형 격자이다. 농부는 먼저 초기 밭들의 집합을 사며, 그의 경작지(parcel) 는 처음에는 정확히 이 밭들로 이루어진다. 최종 경작지는 말뚝과 끈을 이용해 다음 과정을 반복하여 정해진다.

1. 현재 경작지에 속한 모든 밭의 중심에 말뚝을 하나씩 박는다.
2. 말뚝들을 끈으로 둘러싸, 모든 말뚝을 감싸는 가장 작은 영역(말뚝들의 볼록 껍질)을 만든다.
3. 새로운 경작지는 이 영역과 넓이가 겹치는(교집합의 넓이가 0이 아닌) 모든 밭들의 집합이다. 영역과 변 하나 또는 꼭짓점 하나만 맞닿는 밭은 포함되지 않는다.

경작지는 오직 커지기만 하므로, 경작지가 더 이상 변하지 않을 때까지 위 과정을 반복한다. 이렇게 얻어진 경작지를 최종(final) 경작지라고 한다.

흥미롭게도, 초기 밭들 중 일부만 샀더라도 완전히 같은 최종 경작지에 도달하는 경우가 있다. 초기 밭들의 어떤 부분집합에서 시작했을 때 얻는 최종 경작지가, 초기 밭 전체에서 시작했을 때의 최종 경작지와 정확히 같으면, 그 부분집합을 유효한(valid) 부분집합이라고 한다. 농부는 유효한 부분집합이 몇 개인지 알고 싶어 한다.

입력은 여러 개의 독립적인 테스트 케이스로 이루어져 있으며, 각각을 모두 해결해야 한다.

첫째 줄에 테스트 케이스의 수 $Z \le 50$ 가 주어진다. 각 테스트 케이스는 다음 형식으로 주어진다.

각 테스트 케이스의 첫째 줄에는 초기 밭의 수 $n \le 10^6$ 이 주어진다. 이어지는 $n$ 개의 줄에는 각각 두 정수 $x_i$, $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)가 주어지며, 이는 한 초기 밭의 좌표이다. 한 테스트 케이스 안의 모든 초기 밭은 서로 다르다.

각 테스트 케이스마다, 그 초기 밭들의 유효한 부분집합의 개수를 $k$ 라고 할 때, $k \bmod (10^9 + 7)$ 을 한 줄에 출력한다.