미하일 2마리

메이플스토리에는 235레벨 이후에 갈 수 있는 에스페라란 지역이 있다. "거울에 비친 빛의 신전"이 사냥 효율이 상당히 좋아서 인기가 많다. 여기서 사냥하는 것을 신전 사냥이라고 한다. 위의 그림은 해당 지역을 그래프로 나타낸 것이다.

2019년에 이 신전 사냥과 관련된 재밌는 떡밥이 있었다. 보통 2명이서 사냥을 하면 몹 리젠 속도가 2명이 사냥하는 속도를 따라잡지 못해서 비효율적인데, 미하일이란 직업의 경우에는 사냥 능력이 좋지 않아서 미하일 2명이서 사냥할 때는 서로 영향을 받지 않고 사냥할 수 있었다고 알려진 것이다.

그래서 미하일 2명이 파티를 짜고 사냥을 하기로 결심했다. 해당 그림에서 파란색 원 2개로 표기된 곳이 미하일 2명의 사냥 시작점으로 총 n초 동안 다음과 같이 사냥을 할 것이다.

1. 미하일들은 무조건 매 초마다 그림에서 표기된 그래프에 따라서 움직여야 하며, 절대로 가만히 있으면 안 된다.
2. 그래프에서 각 간선의 거리는 전부 1이다.
3. 미하일들은 매 초마다 거리 1만 움직일 수 있다.
4. 미하일의 위치 2곳이 a, b라면 a에서 b로 가는 최단 경로와 b에서 a로 가는 최단 경로의 길이는 각각 3 이상이어야 한다.

이 때, n초 동안 사냥할 수 있는 총 방법 수를 1,000,000,007로 나눈 나머지를 구하시오. 미하일 2명이 각각 위치한 곳이 a, b인 경우와 b, a에 있는 경우는 서로 다른 경우로 취급한다.

첫 번째 줄에 정수 n (1 ≤ n ≤ 1,000,000,000)이 주어진다.

n초 동안 사냥할 수 있는 총 방법 수를 1,000,000,007로 나눈 나머지를 구하시오.