TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4234
  • Problem
  • P4234三角分形
    Limits : Time Limit : - MS   Memory Limit : 265536 KB
    Judgment Tips : 1s
    Description

    今天何老板得到了一个神奇的正三角形,它具有自动分形技能。
    一天后,它会分成4个相同的正三角形,其中三个“尖尖”朝上,一个“尖尖”朝下。
    一天后,里面的每个三角形又会按上述规则分形下去。
    如此反复......
    何老板想知道,在n天后,总共有多少个“尖尖”朝上的三角形。


    分形过程如下图所示,2天后,有10个“尖尖”朝上的三角形。

     

    Input Format

    一行,一个整数n

    Output Format

    一行,一个整数,表示计算结果, mod 1000000007后再输出。

    Sample Input 1

    1

    Sample Output 1

    3

    Sample Input 2

    2

    Sample Output 2

    10

    Sample Input 3

    11

    Sample Output 3

    2098176

    Hint

    对于50%的数据:0 ≤ n ≤ 10^5
    对于100%的数据:0 ≤ n ≤ 10^18


    Source  改编自Codeforces 185A Plant