A22749.栈的操作
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
管理备注:本题因证明难度极高,做题难度低,故评为灰题现在有四个栈,其中前三个为空,第四个栈从栈顶到栈底分别为 1,2,3,⋯,n。每一个栈只支持一种操作:弹出并压入。它指的是把其中一个栈 A 的栈顶元素 x 弹出,并马上压入任意一个栈 B 中。但是这样的操作必须符合一定的规则才能进行。
- 规则 1:A 栈不能为空。
- 规则 2:B 栈为空或 x 比 B 栈栈顶要小。
对于给定的 n,请你求出把第四个栈的 n 个元素全部移到第一个栈的最少操作次数。
由于最少操作次数可能很多,请你把答案对 106+7 取模。
输入格式
一行,一个整数 n。
输出格式
一行,一个正整数,为把最少操作次数 mod(106+7) 的值。
输入输出样例
输入#1
2
输出#1
3
说明/提示
- 对于 30% 的数据,n≤8。
- 对于 60% 的数据,n≤60。
- 对于 100% 的数据,n≤2×109。