최대 단색 클리크

시간 제한2초메모리 제한512 MB

요약

모든 사이클에서 인접한 두 변의 색이 같은 완전 그래프가 주어질 때, 공집합이 아닌 모든 노드 부분집합에 대해 그 안에서 모든 변의 색이 같은 최대 부분집합 크기를 구해 합을 1e9+7로 나눈 나머지를 출력한다.

난이도: 어려움10점 중 9점
유형: 그래프, 조합론, 수학, 동적 계획법
정답자: 아직 제출이 없습니다

문제

노드가 $n$ 개인 무방향 완전 그래프를 발견했다. 노드에는 $1$ 부터 $n$ 까지 번호가 붙어 있다. 각 간선에는 색이 칠해져 있으며, 편의상 색은 $1$ 이상 $300$ 이하의 정수로 나타낸다. 흥미롭게도 이 그래프의 모든 단순 사이클에는 같은 색인 인접한 두 간선이 반드시 존재한다.

노드의 공집합이 아닌 부분집합 $S$ 마다, $S$ 에서 고른 노드들 사이의 간선이 모두 같은 색이 되도록 노드를 고를 때 고를 수 있는 노드의 최대 개수를 $f(S)$ 라고 하자. 노드 하나만 고르는 경우는 항상 조건을 만족한다. 그래프의 공집합이 아닌 모든 노드 부분집합 $S$ 에 대해 $f(S)$ 의 합을 구하시오.

입력

입력은 테스트 케이스 하나로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다.

첫째 줄에 그래프의 노드 수 $n$ ( $1 \le n \le 300$ )이 주어진다.

다음 $n$ 개의 줄에는 각각 정수 $n$ 개가 주어진다. 이 행렬은 간선의 색을 나타내며, $c_{x,y}$ 는 노드 $x$ 와 노드 $y$ 를 잇는 간선의 색이다 ( $0 \le c_{x,y} \le 300$ ). 노드에서 자기 자신으로 가는 간선은 없으므로 대각선의 값은 $0$ 이다 ( $c_{x,x} = 0$ ). 행렬은 대칭이며, 대각선 밖의 색은 $1$ 이상 $300$ 이하이다 ( $x \ne y$ 일 때 $1 \le c_{x,y} = c_{y,x} \le 300$ ).

출력

그래프의 공집합이 아닌 모든 노드 부분집합 $S$ 에 대한 $f(S)$ 의 합을 정수 하나로 출력한다. 이 값은 매우 클 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 출력한다.

예제2

예제 1
입력
```
4
0 1 1 1
1 0 2 2
1 2 0 3
1 2 3 0
```
예상 출력
```
26
```

예제 2

입력

5
0 300 300 300 300
300 0 300 300 300
300 300 0 300 300
300 300 300 0 300
300 300 300 300 0

예상 출력