TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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