飞神

题号：NC218601
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

高飞曾经沉迷于《原神》，但他现在已经弃坑了，因为他要创作一款独立游戏：《飞神》。

这款游戏中，随着等级的提升，装备的属性也会提升。
人物初始会拥有矛和盾两个装备，为了让玩家更肝，高飞把等级的上限设为了 ${10^{18}}$ 级。

对于矛，从第 ${i-1}$ 级升到第 ${i}$ 级需要 ${a_i}$ 点经验值。
对于盾，从第 ${i-1}$ 级升到第 ${i}$ 级需要 ${b_i}$ 点经验值。
如果玩家将矛和盾都从等级 ${i-1}$ 升级到了等级 ${i}$ ，那么玩家将会获得 ${c_i}$ 点成就值。

它们的计算方式如下：

$\left\{ \begin{array}{**lr**} a_1=3, & \\ a_2=4, & \\ a_i=3*a_{i-1}+4*a_{i-2}, & (i\ge 3) \\ b_1=7, & \\ b_2=11, & \\ b_i=4*b_{i-1}+11*b_{i-2}, & (i\ge 3) \\ c_i=a_i*b_i+1, & (i\ge 1) \\ \end{array} \right.$

现在高飞想知道，如果将矛和盾都从等级 ${n-1}$ 升级到了等级 ${n}$ 以后，所能够获得的成就值是多少呢？由于答案可能较大，你只需要输出答案对 ${10^9+7}$ 取余数的结果即可。

输入描述:

输入仅包括一个数字，含义如上所述。

输出描述:

输出一个数字，表示将矛和盾都从等级升级到了等级以后，所能够获得的成就值。

示例1

输入

复制

输出

复制

说明

示例2

输入

复制

输出

复制

说明

示例3

输入

复制

输出

复制

415522536

备注:

由于答案可能较大，你只需要输出答案对取余数的结果。