TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4234
  • 题目
  • P4234三角分形
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

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


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

     

    输入格式

    一行,一个整数n

    输出格式

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

    样例输入 1

    1

    样例输出 1

    3

    样例输入 2

    2

    样例输出 2

    10

    样例输入 3

    11

    样例输出 3

    2098176

    提示

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


    来源  改编自Codeforces 185A Plant