A/virus

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

Sakuyalove finds a triangle pyramid which contains many nodes with its own A/virus value. Out of curiosity, Sakuyalove is trying to calculate the summation of A/virus value in all of the nodes in the pyramid. 

It is noticed that, the triangle pyramid consists of n layers, and the ith layer consists of i nodes. At the top of the triangle pyramid, which is known as the single node in the 1st layer, there is 1 A/virus value in this node. 

As we know, A/virus is contagious, since there are more and more A-soul fans on the planet. During the process of propagation from the top layer to the bottom layer, each node will propagate its A/virus value to its bottom node and its bottom-right node, which means the final A/virus value of certain node is the summation A/virus value of its top node (if it exists) and its top-left node (if it exists). Sakuyalove wants to calculate the summation of A/virus value in all of the nodes in this triangle pyramid to speculate whether the planet can still be saved. Please help her.

Note: Since the summation of A/virus value may be very large, you just need to output the answer modulo 109+7. 

The Input consists of one integer n (1 ≤ n ≤ 1000000).

Output one integer, the summation of A/virus value in the pyramid.

示例1

复制3

3

复制7

7

The pyramid consists of 3 layers, and the A/virus value of every node goes as the following:

1 (first layer)

1 1 (second layer)

1 2 1 (third layer)

The summation of A/virus value in all of the nodes is:

1 + 1 + 1 + 1 + 2 + 1 = 7

//签到题（我只会签到题...）
#include
#include
int main()
{
	int n;
	scanf("%d", &n);
	long long sum = 0, low = 1;
	long long t = pow(10, 9) + 7;
	for (int i = 0; i < n; i++)
	{
        sum += low;
		low = (low % t) * 2;
		sum %= t;
	}
	printf("%lld", sum);
	return 0;
}