#P2026. [SHOI2009]Coin
[SHOI2009]Coin
[SHOI2009] Coin
题目描述
Constantine 想给朋友 YY 买一枚 MySky Island 的纪念币。纪念币的一面刻字,另一面沿圆周等距镶嵌 颗宝石。下面是镶有 颗宝石的例子。

如果旋转纪念币便能使对应位置的颜色完全相同,这两种排布算作同一种。只有翻面后才能重合的两种排布算作不同的排布。下图两种排布可以通过旋转重合。

按照当地习俗,宝石数 必须为奇数。Constantine 选出了 种颜色,要求每种颜色至少出现一次。求可以制作多少种不同的纪念币。
输入格式
输入一行一个正奇数 ,满足 。
输出格式
输出一行恰好 位十进制数字,表示答案的最后 位。实际位数不足时在左侧补 。
17
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020922789888000
相关
在下列比赛中: