题目内容

小红拿到了一个数列，数列的前几项是: { $1,2,4,5,10,11,22,......$ }

这个数列的规律是:

第一个数是 $1$ 。

从第二个数开始，第偶数项比前一个数多 $1$ 。

第奇数项为前一个数乘以 $2$ 。

小红想知道，这个数列的第 $n$ 个数是多少? 由于答案可能过大，请对 $10^9+7$ 取模。

输入描述

一个正整数 $n$

$1 ≤n ≤ 10^5$

一个正整数，代表数列的第 $n$ 项对 $10^9+ 7$ 取模的值。

输入

输出

说明

数列的第 $2$ 项为 $2$

输入

输出

说明

数列的第 $8$ 项为 $23$