뚜루루 뚜루
시간 제한0.5초메모리 제한512 MB
R행 C열 격자에 행 단위로 적힌 "뚜루루뚜루"가 반복되는 글자판 위에서 칸을 반복 방문하지 않고 인접 칸으로만 이동해 철자를 그대로 읽는 길이 10짜리 경로의 개수를 구한다.
문제
요즘 아기 석환이라는 노래가 인기를 끌고 있다. 귀여운 아기 석환 캐릭터가 나오는 동영상과 중독성 있는 뚜루루 뚜루 후렴구가 전국 각지의 학생과 직장인의 마음을 사로잡았다.
강남의 직장인 gs12117도 이 노래에 푹 빠졌다. 특히 후렴구에 중독된 gs12117은 R줄 C칸으로 나뉜 종이에 뚜루루 뚜루 후렴구를 계속 적어 나가기 시작했다. 후렴구를 적을 때는 종이의 첫 줄 가장 왼쪽 칸에서 시작해 오른쪽으로 한 칸에 한 글자씩 뚜, 루, 루, 뚜, 루를 순서대로 적고, 한 줄의 가장 오른쪽 칸에 도달하면 다음 줄의 가장 왼쪽 칸으로 넘어간다.
\n7×7 종이에서의 예시
gs12117은 이 종이에서 뚜루루 뚜루 경로를 많이 찾으려고 한다. 뚜루루 뚜루 경로란 임의의 칸에서 출발해서 이미 방문한 칸을 다시 방문하지 않도록 상하좌우로 이동하면서 각 칸에 적힌 글자를 순서대로 읽었을 때, 그 결과가 정확히 뚜루루 뚜루가 되는 경로를 말한다.
종이의 크기가 주어졌을 때, gs12117이 찾을 수 있는 뚜루루 뚜루 경로의 개수를 구하여라. 어떤 두 경로가 같은 순서에 다른 칸을 방문할 경우 두 경로는 서로 다른 경로이다.
입력
첫 줄에 종이의 줄 수와 칸 수를 의미하는 정수 R과 C(1 ≤ R, C ≤ 12,117)가 주어진다.
출력
첫 줄에 gs12117이 찾을 수 있는 뚜루루 뚜루 경로의 개수를 출력한다.
힌트
첫 번째 예시에서는 다음과 같은 경로들이 가능하다.
