벌집 격자의 8단계 이동

그림과 같이 무한히 이어진 정육각형 격자망 위에 원점 ${\rm O}(0,0)$이 있다. 점 ${\rm P}$가 원점 ${\rm O}$에서 출발하여 $1$초마다 현재 위치와 선분으로 연결된 세 교점 중 하나로 이동한다. 점 ${\rm P}$가 출발한 지 $8$초 후 원점 ${\rm O}$에 있도록 하는 이동 방법의 수를 구하시오. (단, 점 ${\rm P}$는 같은 교점이나 선분을 여러 번 지날 수 있다.)