题目描述

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

这个数列的规律是: 第一个数是1。

从第二个数开始，第偶数项比前一个数多1。第奇数项为前一个数乘以2。

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

输入描述

一个正整数$n(1\le n\le 10^5)$

输出描述

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

样例1

输入

2

输出

2

样例解释

数列的第2项为2

样例2

输入

8

输出

23