题目描述

Dwarfs 种了一株非常有意思的植物，这株植物像一个方向向上的三角形。它有一个迷人的特点，那就是在一年后一株方向向上的三角形的植物就会被分成 $4$ 株三角形的植物：它们当中的三株方向是向上的，一株方向是向下的。又一年之后，每株植物都会分成四个，规则如上。之后的每年都会重复这一过程。下面的图说明了这一发展过程。

请帮助 Dwarfs 算出 $n$ 年后将会有多少个方向向上的三角形。

PS：可能直译会造成某些地方比较难理解，直接理解成三角形和植物是一个东西就可以了。

输入格式

第一行包括一个整数 $n\ (0\leq n\leq 10^{18})$，即这植株生长的总年份。

输出格式

输出一个整数，即 $n$ 年后向上的三角形的个数，答案对 $10^{9}+7$ 取模。

1

3

2

10