Kolya 喜欢把侏儒放在圆桌上并给他们硬币,而 Tanya 喜欢研究坐在等边三角形顶点上的三胞胎侏儒。
更正式地说,有 3n 个侏儒围成一圈。每个侏儒可以拥有 1 到 3 个硬币。让我们按照 0 到 3n - 1 之间的数字对这些位置进行编号,让坐在第 i 个位置的侏儒拥有 ai 硬币。如果存在整数 i (0 ≤ i < n) 使得 ai + ai + n + ai + 2n ≠ 6,则满足 Tanya。
计算选择 ai 的方式有多少种,以便 Tanya 满意。由于分配硬币的方式可以有多种,请打印该数字模 109 + 7 的余数。如果存在索引 i (0 ≤ i < 3n),则 a 和 b 两种方式被认为是不同的,这样 ai ≠ bi (也就是说,某些侏儒以这两种方式获得了不同数量的硬币)。
输入
单行包含数字 n (1 ≤ n ≤ 105) — 侏儒的数量除以三。
输出
打印一个数字——满足 Tanya 模 109 + 7 的分配硬币变体数量的余数。
示例
输入 #1
1
输出 #1
20
输入 #2
2
输出 #2
680
注意
n = 1 的 20 种方式(索引为 0 的侏儒位于三角形的顶部,侏儒 1 位于右顶点,侏儒 2 位于左顶点):