15505번 - 아름다운 퍼즐 만들기

성용이는 생일선물로 N * M 형태의 퍼즐 판과 빨강,파랑,초록,노랑 색의 1 * 1 크기의 무한히 많은 퍼즐 조각을 받았다.

성용이는 이 퍼즐조각들을 사용하여 퍼즐을 최대한 아름답게 꾸밀려고 한다. 상하좌우로 인접한 칸들이 전부 서로 다른 색깔이어야 알록달록하고 보기 좋기 때문에, 성용이는 서로 인접해있는 칸끼리는 다른 색깔의 퍼즐 조각을 사용하려고 한다.

성용이는 퍼즐을 어떻게 꾸미면 가장 아름다운 퍼즐이 나올지 궁금해졌다. 퍼즐 전체의 아름다움은 각 위치에 사용된 퍼즐 조각의 아름다움의 합으로 정의된다고 했을 때, 퍼즐의 최대 아름다움과 그런 아름다움을 만들 수 있는 경우의 수를 구하는 프로그램을 작성해보자.

첫째 줄에 N(1 ≤ N ≤ 10), M(1 ≤ M ≤ 10) 이 주어진다.

둘째 줄 부터 N 줄에 걸쳐, 퍼즐 판의 각 위치에 빨강색 퍼즐조각을 사용했을 때 얻을 수 있는 아름다움이 주어진다.

그 다음 N 줄에 걸쳐, 퍼즐 판의 각 위치에 파랑색 퍼즐조각을 사용했을 때 얻을 수 있는 아름다움이 주어진다.

그 다음 N 줄에 걸쳐, 퍼즐 판의 각 위치에 초록색 퍼즐조각을 사용했을 때 얻을 수 있는 아름다움이 주어진다.

그 다음 N 줄에 걸쳐, 퍼즐 판의 각 위치에 노랑색 퍼즐조각을 사용했을 때 얻을 수 있는 아름다움이 주어진다.

각 퍼즐 조각의 아름다움의 크기는 0이상 10⁹ 이하이다.

퍼즐의 아름다움의 최대크기와 최대 아름다움을 만들 수 있는 방법의 개수를 출력한다. 최대 아름다움을 만들 수 있는 방법의 개수는 굉장히 커질 수 있기 때문에, 10⁹ + 7로 나눈 나머지를 출력한다.

퍼즐의 아름다움의 최대크기는 21억을 넘지 않음이 보장된다.

네 종류의 색깔을 각각 R,B,G,Y라고 했을 때,

첫 번째 예시에는 첫 칸에 R,G,B,Y중 어느 칸을 배치해도 전체 아름다움은 1이고 이 경우가 최대다. 따라서 총 4가지의 경우가 존재한다.

두 번째 예시에서는
RB
GY
로 배치했을 때 2+2+2+2 = 8로 최대의 아름다움을 만들 수 있고, 이렇게 만들 수 있는 경우의 수는 한 가지 밖에 없다.