만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

넴모넴모 (Easy)

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

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

쉬움10점 중 3점

유형
완전 탐색, 비트 연산, 조합론, 수학
정답자
아직 제출이 없습니다

문제

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

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

입력

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

출력

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

힌트

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

예제3

  1. 예제 1

    입력
    2 2
    
    예상 출력
    15
    
  2. 예제 2

    입력
    2 3
    
    예상 출력
    57
    
  3. 예제 3

    입력
    3 5
    
    예상 출력
    22077