E:禁止套娃
题号:NC206044
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

一个集合中,任何两个元素都认为是不相同的,即每个元素只能出现一次。

子集是一个数学概念:如果集合A的任意一个元素都是集合B的元素,那么集合A称为集合B的子集。

现在有这么一个问题,一个整数的子集的子集一共有多少个。

比如说{1,2}这个集合,他的子集有 {空},{1}, {2}, {1,2}这4个子集。

这4个子集的子集分别是

{空}

{空},{1}

{空},{2}

{空},{1}, {2}, {1,2}

所以{1,2}这个集合的子集的子集个数有9个。

输入描述:

输入只有一个数n,代表这个集合里面元素的个数是n个(1<=n<1e9)。

输出描述:

输出包含一个数,表示输入的集合子集的子集个数。结果可能很大,结果需要对1e9+7进行取余后再输出。
示例1

输入

复制
2

输出

复制
9