cho.sh뚜루루 뚜루
뚜루루 뚜루가 반복되어 적힌 R x C 종이에서 같은 칸을 두 번 지나지 않으면서 글자가 뚜루루 뚜루가 되는 5칸 경로의 개수를 센다.
어려움8조합론수학행렬완전 탐색아직 제출이 없습니다시간 제한0.5초메모리 제한512 MB문제
최근 아기 석환이라는 노래가 큰 인기를 끌고 있다. 이 노래는 귀여운 아기 석환 캐릭터가 등장하는 동영상과 중독성 있는 뚜루루 뚜루 후렴구로 전국 각지의 학생들과 직장인들의 마음을 사로잡았다.
강남의 직장인 gs12117 역시 이 노래에 흠뻑 빠졌다. 특히 이 노래의 후렴구에 중독된 gs12117은 R줄 C칸으로 나뉘어진 종이에 뚜루루 뚜루 후렴구를 계속해서 적어 나가기 시작했다. 후렴구를 적을 때는 종이의 첫 줄 가장 왼쪽 칸에서부터 오른쪽으로 한 칸에 한 글자씩 뚜, 루, 루, 뚜, 루를 순서대로 적어 나가며, 한 줄의 가장 오른쪽 칸에 도달하면 다음 줄의 가장 왼쪽 칸으로 넘어간다.
7×7 종이에서의 예시
gs12117은 이 종이에서 뚜루루 뚜루 경로를 많이 찾으려고 한다. 뚜루루 뚜루 경로란 임의의 칸에서 출발해서 이미 방문한 칸을 다시 방문하지 않도록 상하좌우로 이동하면서 각 칸에 적힌 글자를 순서대로 읽었을 때, 그 결과가 정확히 뚜루루 뚜루가 되는 경로를 말한다.
종이의 크기가 주어졌을 때, gs12117이 찾을 수 있는 뚜루루 뚜루 경로의 개수를 구하여라. 어떤 두 경로가 같은 순서에 다른 칸을 방문할 경우 두 경로는 서로 다른 경로이다.
입력
첫 줄에 종이의 줄 수와 칸 수를 의미하는 정수 R과 C(1 ≤ R, C ≤ 12,117)가 주어진다.
출력
첫 줄에 gs12117이 찾을 수 있는 뚜루루 뚜루 경로의 개수를 출력한다.
힌트
첫 번째 예시에서는 다음과 같은 경로들이 가능하다.
