Description

There are four stacks. The first three are empty, and the fourth stack contains, from top to bottom, $1,2,3,\cdots ,n$. Each stack supports only one operation: pop and push. This means popping the top element $x$ from some stack A and immediately pushing it onto any stack B. However, such an operation is allowed only if the following rules are satisfied.

• Rule $1$: Stack A must be non-empty.
• Rule $2$: Stack B is empty, or $x$ is smaller than the top of stack B.

Given $n$, find the minimal number of operations needed to move all $n$ elements from the fourth stack to the first stack.

Since the minimal number of operations can be very large, output the answer modulo $10^6+7$.

Input Format

One line containing an integer $n$.

Output Format

One line containing a positive integer, the value of the minimal number of operations $\bmod (10^6+7)$.

2

3

Hint

• For 30% of the testdata, $n \le 8$.
• For 60% of the testdata, $n \le 60$.
• For 100% of the testdata, $n \le 2 \times 10^9$.

Translated by ChatGPT 5