题目描述

现在有四个栈，其中前三个为空，第四个栈从栈顶到栈底分别为1,2,3,…,n。每一个栈只支持一种操作：弹出并压入。它指的是把其中一个栈A的栈顶元素x弹出，并马上压入任意一个栈B中。
但是这样的操作必须符合一定的规则才能进行。
规则1：A栈不能为空。
规则2：B栈为空或x比B栈栈顶要小。
对于给定的n，请你求出把第四个栈的n个元素全部移到第一个栈的最少操作次数。
由于最少操作次数可能很多，请你把答案对1000007取模。

输入格式：

一行，一个n

输出格式：

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

输入样例#1：

2

输出样例#1：

3