#P2026. [SHOI2009]Coin

    ID: 1049 传统题 2000ms 64MiB 尝试: 42 已通过: 16 难度: 8 上传者: 标签>难度分类提高+/省选-组合数学Burnside 引理容斥原理数论欧拉函数约数成对枚举试除法分解质因数Pascal 递推快速幂同余的加减乘运算模拟与实现技巧高精度乘法高精度除法CF2400Polya

[SHOI2009]Coin

[SHOI2009] Coin

题目描述

Constantine 想给朋友 YY 买一枚 MySky Island 的纪念币。纪念币的一面刻字,另一面沿圆周等距镶嵌 nn 颗宝石。下面是镶有 77 颗宝石的例子。

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

按照当地习俗,宝石数 nn 必须为奇数。Constantine 选出了 1717 种颜色,要求每种颜色至少出现一次。求可以制作多少种不同的纪念币。

输入格式

输入一行一个正奇数 nn,满足 1≤n≤1091\le n\le10^9。

输出格式

输出一行恰好 120120 位十进制数字,表示答案的最后 120120 位。实际位数不足时在左侧补 00。

17
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020922789888000