Description

Lh：粉兔你教我一下抽屉原理吧

Clz：就是给你一个长度为 $n$ 的序列，每个数只能取 $0,1,2$，那你连续取三个数必然有两个相等……

Lh：等等你梭啥，再说一遍

Clz：……$\mathrm{emmm}$ 当我没说

Marser：就是一个序列，对于每一个连续三元组都要满足其中至少有两个相等

现在粉兔问你：有多少个长度为 $n$ 的序列满足粉兔的要求？请对 $19260817$ 取模。

Input Format

从文件 ioi.in 中读入。

一行一个正整数，$n$。

Output Format

输出到文件 ioi.out 中。

一行一个整数，含义如题。

Sample

样例输入

4

样例输出

51

样例解释

$51$ 种序列如下：

$[0,0,0,0]$,$[0,0,0,1]$,$[0,0,0,2]$,$[0,0,1,0]$,$[0,0,1,1]$,$[0,0,2,0]$,$[0,0,2,2]$,$[0,1,0,0]$,$[0,1,0,1]$,$[0,1,1,0]$,$[0,1,1,1]$,$[0,1,1,2]$,$[0,2,0,0]$,$[0,2,0,2]$,$[0,2,2,0]$,$[0,2,2,1]$,$[0,2,2,2]$,$[1,0,0,0]$,$[1,0,0,1]$,$[1,0,0,2]$,$[1,0,1,0]$,$[1,0,1,1]$,$[1,1,0,0]$,$[1,1,0,1]$,$[1,1,1,0]$,$[1,1,1,1]$,$[1,1,1,2]$,$[1,1,2,1]$,$[1,1,2,2]$,$[1,2,1,1]$,$[1,2,1,2]$,$[1,2,2,0]$,$[1,2,2,1]$,$[1,2,2,2]$,$[2,0,0,0]$,$[2,0,0,1]$,$[2,0,0,2]$,$[2,0,2,0]$,$[2,0,2,2]$,$[2,1,1,0]$,$[2,1,1,1]$,$[2,1,1,2]$,$[2,1,2,1]$,$[2,1,2,2]$,$[2,2,0,0]$,$[2,2,0,2]$,$[2,2,1,1]$,$[2,2,1,2]$,$[2,2,2,0]$,$[2,2,2,1]$,$[2,2,2,2]$。

Hint

对于 $30\%$ 的数据，$n \leq 10$。
对于 $60\%$ 的数据，$n \leq 10^6$。
对于 $100\%$ 的数据，$3 \le n \leq 10^{18}$。