题目描述

在新建成的城市数学文化馆中，最引人注目的是一面宏大的展示墙。这面墙上嵌有一个特殊的矩形区域：它由两行瓷砖构成，每行有 $N$ 个格子，整体呈现出一个 $2 \times N$ 的方格结构。为了致敬数学家欧几里得对数论的贡献，设计师构思了一项美学方案：他们计划使用三种特制的数字瓷砖——分别印有 $6$、$1$ 和 $5$，来填满这些格子，使得任意两个相邻瓷砖上的数字互质。

瓷砖之间共有两种相邻关系：横向相邻（同一行中左右相邻的瓷砖）和纵向相邻（同一列中上下相邻的瓷砖）。无论是哪种相邻关系，它们所承载的数字都必须满足互质条件。

作为受邀的技术顾问，现在，请你计算出在严格遵循上述互质规则的前提下，共有多少种不同的瓷砖填充方法。由于答案可能很大，你只需给出其对 $10^9 + 7$ 取余后的结果即可。

输入格式

输入一个整数 $N$，表示矩形区域的列数。

输出格式

输出一个整数，表示符合互质条件的瓷砖填充方法的数量，对 $10^9 + 7$ 取余后的结果。

1

7

2

35

提示

【评测用例规模与约定】

对于 $10\%$ 的评测用例，$1 \leq N \leq 10$。

对于 $100\%$ 的评测用例，$1 \leq N \leq 10^5$。