← 返回题目列表

Codeforces · 185/A

A. 工厂

中文机器翻译题面 查看原题

小矮人种了一种非常有趣的植物,它是一个“向上”的三角形。这种植物有一个有趣的特点。一年后,“向上”的三角形植物会分成四个三角形植物:其中三个将指向“向上”,一个将指向“向下”。又过一年,每个三角形植物会分裂成四个三角形植物:其中三个将与亲本植物朝向相同的方向,而其中一个将朝向相反的方向。然后每年都会重复这个过程。下图说明了这个过程。

帮助小矮人找出n年后会有多少棵指向“向上”的三角形植物。

输入

第一行包含一个整数 n (0 ≤ n ≤ 1018) — 植物生长的完整年数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

打印一个整数 — n 年内指向“向上”的植物数量除以 1000000007 (109 + 7) 的余数。

示例

输入 #1

1

输出 #1

3

输入 #2

2

输出 #2

10

注意

第一个测试样本对应于声明中图中的第二个三角形。第二个测试样本对应于第三个测试样本。