#CS1617. 位串

位串

题目背景

翻译自 CSES-1617 题。

题目描述

你的任务是计算长度为 n 的二进制串的数目。例如，当 n=3 时，有 8 个二进制串，分别为 0,001,010,011,100,101,110,10,001,010,011,100,101,110,10,001,010,011,100,101,110,1。

输入格式

输入一个正整数 n。

输出格式

输出一行一个整数，表示答案  mod 109+7\bmod 10^9+7mod109+7 的结果。

样例

3

8

说明/提示

1≤n≤106。