도형이는 최근에 M×N(1 ≤ M ≤ 12, 1 ≤ N ≤ 12)짜리 땅을 샀다. 도형이는 여기에 목장을 만들기 위해 한 칸 씩 격자모양으로 우리를 만들려고 한다. 그런데 땅이 울퉁불퉁해서 땅의 일부분에는 우리를 만들 수 없다.

소들은 사이가 별로 좋지 않아서 서로 인접한 우리에 넣어두면 싸움을 한다는 사실을 알게 되었다. 그래서 도형이는 인접하지 않는 우리에만 소들을 배치하기로 했다. 도형이는 이렇게 소들을 배치할 수 있는 방법이 모두 몇 가지인지 궁금해졌다.

소들을 한 마리도 배치하지 않는 것도 한 가지의 방법으로 포함을 시키고 소들을 배치할 수 있는 방법이 몇 가지인지 구하는 프로그램을 작성해 보자.

목장 timer 1s memory 32MB

목장 1s 32MB