题目描述

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

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

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

求满足 $|p_i-i| \le 1$ 的 $1 \sim n$ 的排列 $\{p_n\}$ 的个数，答案对 $10^8$ 取模。

输入格式

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

输出格式

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

3

3

987

223731

提示

【样例解释 $1$】

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

【数据规模】

对于 $30\%$ 的数据，$n \le 10^6$。

对于 $50\%$ 的数据，$n \le 10^{16}$。

对于 $100\%$ 的数据，$1 \le n \le 10^{1000}$。