Necklace of Beads
题号：NC232529
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出红，绿，蓝3种颜色 的n个珠子，求能够组成多少个不同的项链。 （旋转 和 翻转后 相同的属于同一个项链）
下图是和的一种合法情况。

输入描述:

输入一个正整数。

输出描述:

输出一行表示答案。
示例1

输入

复制 
4

输出

复制 
21
示例2

输入

复制 
5

输出

复制 
39

备注:

原题链接：http://poj.org/problem?id=1286