새로운 서커스 공연

서커스단에서 일하는 창호는 지금까지보다 훨씬 더 드라마틱한 공연을 만들고 싶어합니다.

새로운 공연의 무대 배열은 $N$개의 플랫폼이 원형으로 배열된 형태입니다. 각 플랫폼에서는 $1$에서 $N$명의 단원들이 수직으로 겹쳐있어야합니다. 창호가 신호를 주면 모든 단원이 동시에 시계 방향으로 내려와야 합니다. 이때 스택의 맨 아래의 단원은 움직이지 않고 그 위의 단원은 한 칸, 그 다음 단원은 두 칸 시계 방향으로 이동하는 식입니다. 기술적으로 단원들은 이 동작이이 문제가 없다는 것을 알고 있습니다. 각각의 단원은 떨어질 때, 서로 방해되지 않으므로 모든 단원은 의도한 플랫폼에 착륙할 수 있습니다. 플랫폼에 착륙하는 모든 단원들은 넘어지지 않는 새로운 스택 형태의 무리를 형성합니다.

창호는 단워들이 내려온 후 각 플랫폼에서 새로 형성된 무리가 해당 플랫폼의 원래 무리와 같은 수의 단원을 포함하면 더 드라마틱하고 좋을 것이라고 생각합니다. 이 조건을 만족하는 스택 크기의 구성을 '마법'의 구성이라고 부릅니다. '마법'같은 구성의 수를 계산하여 창호를 도와주세요. 숫자는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 계산하십시오.

한 플랫폼에서 구성이 다른 단원의 수를 할당하는 경우 두 구성은 다르게 간주됩니다.

입력은 단일한 정수, $N$ ($1 \leq N \leq 10^{12}$)입니다.

마법의 구성의 수를 $10^9 + 7$로 나눈 나머지를 나타내는 단일 정수입니다.