아이템 배치

아래와 같은 크기의 격자판이 있다. 행 열에 있는 칸을 라고 표기하자. 예를 들어 “시작" 칸은 , “끝" 칸은 이다.

철수는 현재 칸에 있으며, 칸에 도착하려고 한다. 철수는 아래 세 가지 규칙을 모두 지키면서 이동해야 한다.

• 철수가 현재 칸에 있다면, 또는 로만 이동할 수 있다.
• 철수는 위의 그림에서 X 표시된 칸 , , , , , , , 으로는 이동할 수 없다.
• 철수는 격자판 바깥으로 이동할 수 없다.

가능한 이동 방법 중 하나는 아래와 같다.

격자판에서 “시작", “끝", “X” 칸을 제외한 빈 칸은 총 46개 있다.

당신은 각각의 빈 칸에 아이템을 넣거나, 아이템을 넣지 않을 수 있다. 따라서, 아이템을 배치하는 모든 경우의 수는 가지이다.

철수가 이동하다가 아이템이 있는 칸에 도착하면, 해당 칸에 있는 아이템을 수령한다. 당신은 철수가 규칙을 지키면서 이동하면 항상 정확히 한 개의 아이템만 수령하도록 아이템들을 배치하고자 한다.

예를 들어, 아래 그림의 “ITEM” 표시된 칸에 아이템을 배치하면 철수가 어떤 경로로 이동하는지와 관계 없이 반드시 한 개의 아이템을 수령한다.

아이템을 배치하는 가지의 방법 가운데, 철수가 규칙을 지키면서 어떻게 이동하더라도 정확히 한 개의 아이템을 수령하도록 하는 방법의 수를 구하라.