题目描述

小Z家的地下室里并排放n个小方块（小Z是一位MC狂热爱好者，喜欢用小方块装饰他家的地下室），并且每个方块都不一样（小Z喜欢各不相同的东西），比如有草方块、大理石、黑曜石等。

小Z喜欢以一种特殊的顺序摆放这些小方块，比如：草方块、大理石、黑曜石。一天，小D帮助小Z整理地下室，可是智商捉急的小D将所有小方块搬出来后忘记了它们原来的具体位置，凭着模糊的印象，他可能把原来放在第i个位置上的小方块放到第（i-1）、i、（i+1）个位置中的任意一个上（当然，第1个不可能放到第0个位置上，第n个不可能放到第（n+1）个位置上），比如（对应上面那个例子）：大理石、草方块、黑曜石。

小Z是一个心胸宽广的人，他希望计算一下小D一共会有几种可能的摆放结果，并不追究小D的责任（追究了只会更乱……）。由于他自己的智商也比较捉急，所以如果答案很大的话他只想看到最后的8位（前导零就不要给他看了）。

输入格式

一行，一个正整数n，代表小Z家的地下室一共有n个小方块。

输出格式

一行，一个正整数，表示小D一共有几种可能的摆放结果，只输出后8位，前导零不输出。

3

3

987

223731

提示

【样例解释1】

接着题目中的例子，一共有3种：（草方块，大理石，黑曜石）、（大理石，草方块，黑曜石）、（草方块，黑曜石，大理石）。

【样例解释2】

一共有……00223731种摆放结果，由于前导零不输出，因此输出223731。

【数据规模】

一共有50个测试点。

其中第1~15个：1<n<=10^6

其中第16~25个：10^6<n<=10^16

其中第26~50个：10^16<n<=10^1000

【时空限制】

0.2s/64MB