小矮人种了一种非常有趣的植物,它是一个“向上”的三角形。这种植物有一个有趣的特点。一年后,“向上”的三角形植物会分成四个三角形植物:其中三个将指向“向上”,一个将指向“向下”。又过一年,每个三角形植物会分裂成四个三角形植物:其中三个将与亲本植物朝向相同的方向,而其中一个将朝向相反的方向。然后每年都会重复这个过程。下图说明了这个过程。
帮助小矮人找出n年后会有多少棵指向“向上”的三角形植物。
输入
第一行包含一个整数 n (0 ≤ n ≤ 1018) — 植物生长的完整年数。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
输出
打印一个整数 — n 年内指向“向上”的植物数量除以 1000000007 (109 + 7) 的余数。
示例
输入 #1
1
输出 #1
3
输入 #2
2
输出 #2
10
注意
第一个测试样本对应于声明中图中的第二个三角形。第二个测试样本对应于第三个测试样本。