В двумерной вселенной звезда может быть представлена как точка \((x,y)\) на двумерной плоскости. Две звезды соединены напрямую, если и только если их \(x\) или \(y\) координаты одинаковы, и между ними нет других звезд на отрезке. Определим галактику как связную компоненту, состоящую из звезд, соединенных напрямую или косвенно (через другие звезды).
Для набора звезд его значение определяется как минимальное количество галактик, которое можно получить для этого набора, после выполнения следующей операции любое (возможно, нулевое) количество раз: в рамках операции вы можете выбрать точку \((x,y)\), в которой нет звезды. Если звезда, созданная в этой точке, может быть соединена напрямую как минимум с \(3\) звездами, то вы создаете в этой точке звезду.
Вам дана матрица \(a\) размера \(n\times n\), состоящая из \(0\) и \(1\) и описывающая набор звёзд \(S\). Звезда находится в \((x,y)\) тогда и только тогда, когда \(a_{x,y}=1\). Вычислите сумму значений всех непустых подмножеств \(S\) по модулю \(10^9 + 7\).
Выходные данные
Для каждого набора входных данных выведите сумму значений всех непустых подмножеств \(S\) по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных \(S\) пусто. У \(S\) нет непустых подмножеств. Поэтому ответ \(0\).
Во втором наборе входных данных \(S = \{(1,2),(2,1)\}\). У \(S\) есть \(3\) непустых подмножества.
- \(\{(1,2)\}\) и \(\{(2,1)\}\) — в наборе только одна звезда, образующая \(1\) галактику.
- \(\{(1,2),(2,1)\}\) — две звезды в наборе не соединены, образуя \(2\) галактики.
Таким образом, ответ равен \(1+1+2=4\).
В третьем наборе входных данных \(S = \{(1,2),(3,1),(3,3)\}\). У \(S\) есть \(7\) непустых подмножеств.
- \(\{(1,2)\}\), \(\{(3,1)\}\) и \(\{(3,3)\}\) — в наборе только одна звезда, образующая \(1\) галактику.
- \(\{(1,2),(3,1)\}\) и \(\{(1,2),(3,3)\}\) — две звезды в наборе не соединены, образуя \(2\) галактики.
- \(\{(3,1),(3,3)\}\) — две звезды в наборе соединены, образуя \(1\) галактику.
- \(\{(1,2),(3,1),(3,3)\}\) — изначально звезда \((1,2)\) не входит в галактику, образованную \((3,1)\) и \((3,3)\). Вы можете выполнить операцию, создав звезду в \((3,2)\), соединяющую эти три звезды, образуя \(1\) галактику.
Таким образом, ответ равен \(1+1+1+2+2+1+1=9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
1
0
2
01
10
3
010
000
101
4
0110
1001
1001
0110
11
11111110111
10000010010
10111010011
10111010011
10111010001
10000010000
11111110101
00000000111
11011010011
10010101100
11101010100
11
11011111110
10010000010
00010111010
10010111010
01010111010
11010000010
01011111110
11000000000
01010000010
01000111100
00000001010
11
11010101001
11001010100
00000000110
11111110010
10000010010
10111010110
10111010111
10111010010
10000010110
11111110100
00000000000
3
111
100
111
|
0
4
9
355
593092633
438667113
922743932
155
|