전구 교체

전구 하나를 갈아 끼우는 데는 보통 한 사람이면 충분합니다. 하지만 천장이 너무 높으면 벌써 다섯 사람이 필요합니다. 한 사람이 탁자 위에 올라가 전구를 들고, 나머지 네 사람이 탁자를 돌립니다.

천장이 더 높다면 한 단계 더 나아갈 수 있습니다. 한 사람이 전구를 들고, 네 사람이 탁자를 붙잡되, 그 네 사람도 저마다 다시 탁자 위에 올라서 있으며 그 탁자는 또 다른 네 사람이 붙잡습니다. 이렇게 하면 모두 $1 + 4 + 16 = 21$명이 됩니다. 이 방법은 천장 높이에 따라 얼마든지 확장할 수 있습니다.

일반적으로 $k$번째 단계에서는 새로 $4^{k-1}$명이 필요하므로, $A$단계짜리 구조물을 세우는 데 필요한 사람은 모두 $1 + 4 + 16 + \dots + 4^{A-1}$명입니다. 주어진 높이(단계 수)의 구조물을 세우는 데 필요한 사람 수를 구하세요. 결과가 매우 클 수 있으므로 $500000009$로 나눈 나머지를 출력하면 됩니다.

입력은 정수 $A$ ($1 \le A \le 1000000$) 하나로 이루어지며, 도달해야 하는 구조물의 단계 수를 나타냅니다.

전구를 교체하는 데 필요한 최소 인원 수를 $500000009$로 나눈 나머지를 출력합니다.