题目描述

小 H 生活在三维空间中，但他不喜欢三维空间，他喜欢二维平面。于是他创造了一个二维平面。

小 H 觉得这个平面过于无趣，于是加入了三面镜子，你可以将每面镜子视为平面上的一条线段。

小 H 将三面镜子摆成了正三角形，三面镜子的镜面都朝向三角形内部，且三面镜子的三个角都是开口的（光线可以从其中通过）。

小 H 现在从三角形的一个顶点处向内射入一条光线，他想知道，存在多少种不同的光路，使得这条光线恰好反射 $n$ 次后从射入的顶点射出。请你帮助他解决这个问题。

两条光路不同，当且仅当两条光路不完全重合。

输入格式

一行一个正整数表示 $n$。

输出格式

一行一个整数表示答案。

样例一

输入

7

输出

2

样例二

输入

124111

输出

20686

限制与约定

提示：你可以使用 C++ 中的 __int128 类型来存储 $[-2^{127},2^{127})$ 范围内的整数。