16129번 - 뚜루루 뚜루

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

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

7×7 종이에서의 예시  

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

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

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

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

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