题目描述

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

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

由于最少操作次数可能很多，请你把答案对1000007取模。

输入格式

一行，一个n

输出格式

一行，一个正整数，为把最少操作次数 mod 1000007的值

2

3

提示

对于30%的数据，n<=8

对于60%的数据，n<=60

对于100%的数据，n<=2*10^9