题目描述

在美丽的尧山，有一个大广场，50周年校庆的时候Solo就在大广场上见证了史上最壮观的焰火。
在广场上有一排方砖，现在学校觉得之前喷的颜色不好看了，需要全部重新喷。如今我们有三种颜色的涂料可用（红、绿和白）。但是校方要求白色的方砖的个数不能为奇数。但是现在Solo并不知道一共有多少个方砖，而Solo却想要知道有多少种方法来涂这一排方砖。现在你的任务是猜想一下在任意方砖数目下的方案数。

输入描述

输入只有一个整数n (1≤n≤10000)，表示方砖的数目。

输出描述

输出有n块方砖数目下的方案数。

示例

提示

input

17

output

64570082

相关标签