소 탑 쌓기 묘기

소가 농장 생활에 싫증이 나서 가진 것을 모두 팔고 순회 서커스단에 들어갔다. 지금까지 맡은 묘기는 횃불 저글링, 외줄 타기, 외발자전거 타기처럼 쉬운 것뿐이라 발굽 솜씨 좋은 소에게는 어려울 게 없었다. 단장은 다음 공연에서 훨씬 극적인 묘기를 선보이려 한다.

새 묘기의 무대는 원을 따라 놓인 발판 $N$개다. 각 발판에서 소가 서로의 등에 올라타 탑을 하나씩 쌓고, 탑 하나를 이루는 소는 $1$마리 이상 $N$마리 이하다. 단장이 신호를 보내면 모든 탑이 동시에 시계 방향으로 넘어진다. 탑의 맨 아래 소는 제자리에 있고, 바로 위의 소는 시계 방향으로 발판 한 칸만큼 이동하고, 그다음 소는 두 칸만큼 이동하며, 위로 갈수록 한 칸씩 더 간다. 넘어지는 동안 탑끼리 서로 방해하지 않으므로 모든 소가 목표한 발판에 정확히 내려앉는다. 한 발판에 내려앉은 소는 그 자리에서 새 탑을 이루고, 이 탑은 다시 넘어지지 않는다.

단장은 탑이 넘어진 뒤 모든 발판의 새 탑 크기가 원래 그 발판에 있던 탑 크기와 같으면 묘기가 극적이라고 본다. 이 조건을 만족하는 탑 크기 배치를 마법 배치라고 하자. 마법 배치가 몇 가지인지 세어라. 그 수가 매우 클 수 있으니 $10^9 + 7$으로 나눈 나머지를 구한다.

소의 수가 다른 발판이 하나라도 있으면 두 배치는 서로 다르다.

정수 $N$이 한 줄에 주어진다 ($1 \leq N \leq 10^{12}$).

마법 배치의 개수를 $10^9 + 7$으로 나눈 나머지를 한 줄에 출력한다.

$N = 4$일 때 마법 배치는 $(1,1,1,1)$, $(2,2,2,2)$, $(3,3,3,3)$, $(4,4,4,4)$, $(2,3,2,3)$, $(3,2,3,2)$ 여섯 가지다.