杂技演员
题号:NC212957
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

有一群杂技演员,他们会彼此踩在对方的背上表演杂技。
在A、B、C一共三个舞台上,有n个胖瘦不同的杂技演员,从胖到瘦依次按从下到上的顺序彼此堆叠着在舞台A上表演杂技,他们将借助舞台C,表演将所有演员移动到B舞台上的浮夸操作。
移动有以下规则:
1.每次只能移动一个演员,在移动操作的之前和之后,他必须在舞台的最上方,换句话说,在移动操作的之前和之后,他的背上不能站人。
2.任何时刻不能有一个演员站在一个比他瘦的人的上方,否则这样会把队友踩死(太残忍了~)。

请问需要移动多少步才能将所有演员移动到B舞台上?
答案可能很大,请对1e9+7取模

输入描述:

输入一行一个数n,表示有多少个杂技演员
(1<=n<=1e18)

输出描述:

需要移动的步数(对1e9+7取模)
示例1

输入

复制
1

输出

复制
1

说明

直接将一个杂技演员移动到B轴