← 返回题目列表

Codeforces · 584/B

B. 科利亚和坦尼娅

中文机器翻译题面 查看原题

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 位于左顶点):