넴모넴모 (Easy)

N 곱하기 M 격자에서 2 곱하기 2 정사각형을 이루는 네 칸이 모두 선택되지 않은 부분집합의 개수를 센다. N 곱하기 M은 25 이하다.

쉬움3완전 탐색비트 연산조합론수학아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 격자판과 "넴모"라는 수수께끼의 생물로 하는 "넴모넴모"를 만들었다. 규칙은 아주 간단하다. 격자판의 빈 칸 하나를 골라 "넴모"를 올려놓거나, "넴모"가 놓인 칸 네 개가 2×22 \times 2 정사각형을 이루는 곳을 찾아 그 네 마리를 한꺼번에 없앤다. 이 두 가지를 질릴 때까지 반복하면 된다.

하지만 게임은 정말 재미가 없었고, 네모는 아주 빨리 질려 버리고 말았다. 실망한 네모는 적당히 플레이하다가, "넴모"를 없애고 싶은데 없앨 수 있는 "넴모"가 격자판에 하나도 없으면 게임을 그만두기로 했다. 네모가 게임을 그만두었을 때 나올 수 있는 "넴모" 배치의 가짓수를 구하여라.

입력

첫 번째 줄에 격자판의 행의 개수 NN과 열의 개수 MM이 공백으로 구분되어 주어진다. (1N,M251 \le N, M \le 25, 1N×M251 \le N \times M \le 25)

출력

첫 번째 줄에 주어진 격자판에서 나올 수 있는 배치, 즉 "넴모"가 놓인 칸 네 개가 2×22 \times 2 정사각형을 이루는 곳이 하나도 없는 배치의 가짓수를 출력한다.

힌트

2×22 \times 2 격자판에서는 전체 24=162^4 = 16가지 배치 중 네 칸 모두에 "넴모"가 놓인 한 가지를 뺀 15가지가 조건을 만족한다.