피터는 심심할 때마다, 콩이 하나씩 담긴 그릇을 원형으로 배치합니다. 그런 다음 어느 한 그릇의 콩을 꺼내 시계방향으로 인접한 그릇마다 콩을 하나씩 옮겨 놓습니다. 마지막으로 콩을 옮겨 놓은 그릇의 콩을 꺼내 초기 상태가 될 때까지 이 작업을 반복합니다. 예를 들어 그릇이 5개라면 아래 그림처럼 옮겨 놓습니다:

위 그림처럼 그릇 5개에서 초기 상태가 될 때까지 피터는 15번 작업을 해야 합니다.

M(x)를 x개의 그릇으로 시작해서 다시 초기 상태가 될 때까지 필요한 작업 횟수라고 합시다. 그러면, M(5) = 15 입니다. 또 M(100) = 10920 입니다.

M(2^k+1) 값을 구하세요. 답은 이 값을 7⁹로 나눈 나머지를 제출하세요.