진흥이는 학교의 임원으로 환경개선을 위해 학교 담장을 여러 가지 색깔로 예쁘게 색칠하는 중이다.

지금 색칠하는 부분을 N * M개의 같은 크기의 직사각형 모양으로 나누어서 여러 가지 색깔로 각각의 위치를 칠하려고 한다.

이미 다른 색이 일부 칠해져 있고 이번에는 노란색을 칠할 차례이다.

노란색은 어떤 곳이든 여러 곳에 칠할 수 있지만 어떤 한 곳에 칠해지면 그 곳을 중심으로 상하좌우에는 같은 색을 칠해서는 안된다.

물론 노란색을 아예 칠하지 않을 수도 있다.

진흥이는 문득 현재 상태에서 노란색을 칠할 수 있는 방법이 몇가지나 되는지 궁금해졌다.

처음부터 한가지씩 세어보다가 너무 많아서 그냥은 셀 수 없다는 것을 알게 되었다.

진흥이를 위해 노란색을 칠할 수 있는 방법이 몇 가지인지 계산하는 프로그램을 작성하라.

색칠하기2 timer 1s memory 64MB

색칠하기2 1s 64MB