Informática Intermediário - Semana 53 - Problema 1

Livre de Conjuntos Dominantes

Você possui um conjunto S com N pontos. Um ponto A domina um ponto B se A_x \geq B_x e A_y \geq B_y. Conte o número de subconjuntos não vazios de S que não contenham dois pontos A e B de tal forma que A domine B.

Entrada

A primeira linha contém um único inteiro N, o número de pontos no conjunto S. Cada uma das próximas N linhas contém dois inteiros x e y, representando um ponto nas coordenadas (x, y).

Saída

Imprima o número de subconjuntos não vazios de S que não contenham dois pontos A e B de tal forma que A domine B módulo 10^9+7.

Restrições

  • 1 \leq N \leq 10^5.
  • 1 \leq x_i, y_i \leq 10^5.
  • Todos os N pontos são distintos.

Exemplos

ENTRADA SAÍDA
4
1 1
2 2
3 3
4 4
4
3
2 1
1 1
1 2
4