CF185A.Plant

Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". This plant has an amusing feature. After one year a triangle plant directed "upwards" divides into four triangle plants: three of them will point "upwards" and one will point "downwards". After another year, each triangle plant divides into four triangle plants: three of them will be directed in the same direction as the parent plant, and one of them will be directed in the opposite direction. Then each year the process repeats. The figure below illustrates this process.

Help the dwarfs find out how many triangle plants that point "upwards" will be in n years.

矮人种下了一种非常有趣的植物，其形状是一个朝“上方”指向的三角形。这种植物有一个有趣的特点：一年后，一个朝“上方”指向的三角形植物会分裂成四个三角形植物：其中三个仍朝“上方”指向，一个朝“下方”指向。再过一年，每个三角形植物都会分裂成四个三角形植物：其中三个与母体植物方向相同，一个与母体植物方向相反。此后，该过程每年重复进行。下图展示了这一过程。

请帮助矮人计算 $n$ 年后朝“上方”指向的三角形植物的数量。

The first line contains a single integer n (0 ≤ n ≤ 1018) — the number of full years when the plant grew.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

第一行包含一个整数 $n$（$0 \leq n \leq 10^{18}$）—— 植物完整生长的年数。

请勿在 C++ 中使用 %lld 说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

Print a single integer — the remainder of dividing the number of plants that will point "upwards" in n years by 1000000007 (109 + 7).

输出一个整数——即 n 年后指向“向上”的植物数量对 1000000007（$10^9 + 7$）取模的余数。

The first test sample corresponds to the second triangle on the figure in the statement. The second test sample corresponds to the third one.

第一个测试样例对应题目描述中图示的第二个三角形。第二个测试样例对应图示中的第三个三角形。