На плоскости дано n различных точек с целыми координатами. Для каждой точки можно выполнить одно из трех действий: провести через нее вертикальную прямую, провести через нее горизонтальную прямую или ничего не делать.
Если рассматривать несколько совпадающих прямых как одну, то сколько различных картинок может получиться? Ответ вывести по модулю 109 + 7.
Выходные данные
Вывести количество различных картинок по модулю 109 + 7.
Примечание
В первом примере через точки проходят две вертикальные и две горизонтальные прямые. Существуют способы получить картинку из любого набора этих прямых. В частности, получить картинку на которой нарисованы все четыре прямые можно двумя способами (каждый отрезок обозначает прямую, которой отрезок принадлежит).
Первый способ: 
Второй способ: 
Во втором примере для каждой точки можно независимо выполнить одно из трех действий. Количество картинок равно 32 = 9.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1
1 2
2 1
2 2
|
16
|
|
2
|
2
-1 -1
0 1
|
9
|