#P1573. 栈的操作

栈的操作

题目描述

现在有四个栈,其中前三个为空,第四个栈从栈顶到栈底分别为 1,2,3,,n1,2,3,\cdots ,n。每一个栈只支持一种操作:弹出并压入。它指的是把其中一个栈 A 的栈顶元素 xx 弹出,并马上压入任意一个栈 B 中。但是这样的操作必须符合一定的规则才能进行。

  • 规则 11:A 栈不能为空。
  • 规则 22:B 栈为空或 xx 比 B 栈栈顶要小。

对于给定的 nn,请你求出把第四个栈的 nn 个元素全部移到第一个栈的最少操作次数。

由于最少操作次数可能很多,请你把答案对 106+710^6+7 取模。

输入格式

一行,一个整数 nn

输出格式

一行,一个正整数,为把最少操作次数 mod(106+7)\bmod (10^6+7) 的值。

2
3

提示

  • 对于 30%30\% 的数据,n8n\le 8
  • 对于 60%60\% 的数据,n60n\le 60
  • 对于 100%100\% 的数据,n2×109n\le 2\times 10^9