4005: A魔法部落

Memory Limit：128 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：70 Solved：15

Description

小Biu所在的部落是一个魔法部落，部落中一共有n+1个人，小Biu是魔法部落中最菜的，所以他的魔力值为1，魔法部落中n个人的魔法值都不相同，第一个人的魔法值是小Biu的3倍，第二个人的魔法值是第一个人的3倍，以此类推。 现在小Biu想知道整个部落的魔法值和是多少？由于答案比较大，请把答案对1e9+7取模之后输出。

Input

输入一个数N(0 <= N <= $10^9$)

Output

输出：整个部落的魔法值和模1e9+7。

Sample Input Copy 

3

Sample Output Copy 

40

HINT

样例说明：$3^0+3^1+3^2+3^3 = 1+3+9+27 = 40$ 对于20%的数据，n<=100； 对于40%的数据，n<=1000000； 对于100%的数据，n<=1000000000；

加入题单

算法标签：