소들이 사방치기 게임을 변형해서 하고 있다. 그들은 5x5짜리 격자를 그려서 게임을 하며 각각의 칸에는 수들이 적혀있고, 아무 칸에서나 시작해서 앞, 뒤, 왼쪽, 오른쪽으로(대각선은 불가능하다.) 연속적으로 뛰며, 밟았던 칸을 다시 밟을 수 있다. 이런 식으로 5번 뛸 때, 밟은 6개 칸의 숫자들의 조합으로 6자리 정수를 얻을 수 있다. (단, 000201과 같이 앞에 0이 나올 수 있다.) 이때, 이러한 정수들이 몇 가지나 나올 수 있는지 구하시오.
입력 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 출력 15출력예제 힌트: 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 그리고 212121 이 만들어 질 수 있으며 다른 경우는 없다.
출처: USACO 2005 November Bronze 번역: shinism