A3018. 栈的操作
编程题
普及-
知识点
题目描述
管理备注：本题因证明难度极高，做题难度低，故评为灰题现在有四个栈，其中前三个为空，第四个栈从栈顶到栈底分别为 $1,2,3,\cdots ,n$。每一个栈只支持一种操作：弹出并压入。它指的是把其中一个栈 A 的栈顶元素 $x$ 弹出，并马上压入任意一个栈 B 中。但是这样的操作必须符合一定的规则才能进行。
- 规则 $1$：A 栈不能为空。
- 规则 $2$：B 栈为空或 $x$ 比 B 栈栈顶要小。
对于给定的 $n$，请你求出把第四个栈的 $n$ 个元素全部移到第一个栈的最少操作次数。
由于最少操作次数可能很多，请你把答案对 $10^6+7$ 取模。
- 规则 $1$：A 栈不能为空。
- 规则 $2$：B 栈为空或 $x$ 比 B 栈栈顶要小。
对于给定的 $n$，请你求出把第四个栈的 $n$ 个元素全部移到第一个栈的最少操作次数。
由于最少操作次数可能很多，请你把答案对 $10^6+7$ 取模。
输入格式
一行，一个整数 $n$。
输出格式
一行，一个正整数，为把最少操作次数 $\bmod (10^6+7)$ 的值。
输入输出样例
输入 #1
2
输出 #1
3
说明/提示
- 对于 $30\%$ 的数据，$n\le 8$。
- 对于 $60\%$ 的数据，$n\le 60$。
- 对于 $100\%$ 的数据，$n\le 2\times 10^9$。
- 对于 $60\%$ 的数据，$n\le 60$。
- 对于 $100\%$ 的数据，$n\le 2\times 10^9$。