시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 (추가 시간 없음) 512 MB 186 61 52 45.217%

문제

최근 아기 석환이라는 노래가 큰 인기를 끌고 있다. 이 노래는 귀여운 아기 석환 캐릭터가 등장하는 동영상과 중독성 있는 뚜루루 뚜루 후렴구로 전국 각지의 학생들과 직장인들의 마음을 사로잡았다.

강남의 직장인 gs12117 역시 이 노래에 흠뻑 빠졌다. 특히 이 노래의 후렴구에 중독된 gs12117은 RC칸으로 나뉘어진 종이에 뚜루루 뚜루 후렴구를 계속해서 적어 나가기 시작했다. 후렴구를 적을 때는 종이의 첫 줄 가장 왼쪽 칸에서부터 오른쪽으로 한 칸에 한 글자씩 , , , , 를 순서대로 적어 나가며, 한 줄의 가장 오른쪽 칸에 도달하면 다음 줄의 가장 왼쪽 칸으로 넘어간다.

7×7 종이에서의 예시
7×7 종이에서의 예시  

gs12117은 이 종이에서 뚜루루 뚜루 경로를 많이 찾으려고 한다. 뚜루루 뚜루 경로란 임의의 칸에서 출발해서 이미 방문한 칸을 다시 방문하지 않도록 상하좌우로 이동하면서 각 칸에 적힌 글자를 순서대로 읽었을 때, 그 결과가 정확히 뚜루루 뚜루가 되는 경로를 말한다.

종이의 크기가 주어졌을 때, gs12117이 찾을 수 있는 뚜루루 뚜루 경로의 개수를 구하여라. 어떤 두 경로가 같은 순서에 다른 칸을 방문할 경우 두 경로는 서로 다른 경로이다.

입력

첫 줄에 종이의 줄 수와 칸 수를 의미하는 정수 RC(1 ≤ R, C ≤ 12,117)가 주어진다.

출력

첫 줄에 gs12117이 찾을 수 있는 뚜루루 뚜루 경로의 개수를 출력한다.

예제 입력 1

3 4

예제 출력 1

23

예제 입력 2

5 7

예제 출력 2

162

노트

첫 번째 예시에서는 다음과 같은 경로들이 가능하다.

3×4 종이에서의 예시