레이팅 미적용농장 생활이 지루해진 소들은 세속의 재산을 모두 팔고 순회 서커스단의 단원이 되었다. 지금까지 소들은 쉬운 공연만 맡아 왔다. 횃불 저글링, 줄타기, 외발자전거 타기 등, 발굽이 재주 좋은 소라면 못할 것이 없는 것들이었다. 하지만 단장은 다음 공연을 위해 훨씬 더 극적인 공연을 만들고 싶어 한다.
새 공연의 무대 배치는 원형으로 배열된 \(N\)개의 발판으로 이루어진다. 각 발판 위에는 \(1\)마리 이상 \(N\)마리 이하의 소가 소 위에 소, 그 위에 또 소를 얹는 식으로 탑을 쌓아야 한다. 단장이 신호를 보내면 모든 탑이 동시에 시계 방향으로 무너져야 하는데, 탑의 맨 아래 소는 움직이지 않고, 그 위의 소는 시계 방향으로 한 발판 이동하고, 그다음 소는 시계 방향으로 두 발판 이동하는 식이다. 노련한 체조 선수인 소들은 이 공연의 기술적인 부분에는 아무 문제가 없을 것임을 알고 있다. 소 탑들은 무너질 때 서로 "간섭"하지 않으므로, 모든 소는 의도한 발판에 착지한다. 한 발판에 착지한 모든 소들은 새로운 탑을 이루며, 이 탑은 무너지지 않는다.
단장은 탑들이 무너진 뒤 각 발판의 새 탑이 그 발판의 원래 탑과 같은 수의 소를 가지면 공연이 특히 극적일 것이라고 생각한다. 이 조건을 만족하는 탑 크기의 구성을 "마법 같은" 구성이라고 부른다. 마법 같은 구성의 개수를 계산하여 소들을 도와주자. 이 수는 매우 클 수 있으므로, \(10^9 + 7\)로 나눈 나머지를 계산한다.
두 구성은 어떤 발판에 대해서라도 배정된 소의 수가 다르면 서로 다른 것으로 간주한다.
출제자: Dhruv Rohatgi
출제자: Dhruv Rohatgi
입력은 정수 \(N\) 하나이다 (\(1 \leq N \leq 10^{12}\)).
마법 같은 구성의 개수를 \(10^9 + 7\)로 나눈 나머지를 나타내는 정수 하나를 출력한다.
gymnasts.in · 출력을 쓸 파일 gymnasts.out46For \(N = 4\), the valid configurations are \((1,1,1,1)\), \((2,2,2,2)\), \((3,3,3,3)\),
\((4,4,4,4)\), \((2,3,2,3)\), and \((3,2,3,2)\).
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > February > Platinum