该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

无额外样例。

题目描述

n 个格子围成一圈，第 i （1 ≤ i < n）个和第 i+1 个格子相邻，第 n 个和第 1 个格子相邻。

现在让你往格子里填数，每个格子只能填 1 或 2 或 3 中的一个，不能不填，并且任意两个相邻的格子不能填相同的数字。

问：你有多少种不同的填法？答案可能很大，你需要输出答案 mod $(2^{64})$.

注：两种填法不同，当前仅当至少存在一个格子在两种填法中所填的数字不同。

Input:

多组数据，每组数据占一行，包含一个整数 n

Output:

共 n 行，每组数据的答案占一行.

Sample Input:

1
2
3
31

Sample Output:

3
6
6
2147483646

Hint:

10% 的数据：0 < n ≤ 20

30% 的数据：0 < n ≤ 50

60% 的数据：0 < n ≤ $10^7$

100% 的数据：0 < n ≤ $10^9$， 数据组数不超过 20.