#P2100. 凌乱的地下室
凌乱的地下室
题目描述
小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