Minimum Moves for the Four-Stack Puzzle

You are given four stacks. The first three stacks are initially empty, and the fourth stack contains n elements numbered from 1 to n (from top to bottom). Each stack supports only one operation: pop the top element from one stack A and immediately push it onto another stack B. However, an operation can be performed only if the following rules are satisfied:

• Rule 1: Stack A must not be empty.
• Rule 2: Stack B is empty or the element x (popped from A) is less than the current top element of B.

The goal is to transfer all n elements from the fourth stack to the first stack using the minimum number of operations. Since the answer can be very large, output the answer modulo $10^6+7$.

Hint: This puzzle is analogous to the Tower of Hanoi problem but with four stacks (or pegs) instead of three. The optimal strategy is given by the (conjectured) Frame–Stewart algorithm. Formally, let $dp(0)=0$, $dp(1)=1$, and for $n\ge2$, $$ dp(n)=\min_{1\le k<n} \Bigl\{2\,dp(k)+\Bigl(2^{n-k}-1\Bigr)\Bigr\}. $$ Compute $dp(n)$ and then output $dp(n) \bmod (10^6+7)$.

inputFormat

The input consists of a single integer n representing the number of elements in the fourth stack.

outputFormat

Output a single integer: the minimum number of moves required to transfer all elements from the fourth stack to the first stack, taken modulo $10^6+7$.

sample

1

1