#P5003. 获胜方案
获胜方案
题目描述
乐乐和猫猫在玩一个游戏,先由乐乐在 中选出几组互质的数。例如当 时,乐乐可以选择 中的几组。
然后轮到猫猫。他需要找到一个 使得对于乐乐选择的每组 都满足以下两个条件之一:
例如,如果乐乐选了 ,那么 可以等于 。
如果猫猫找不到满足条件的 值,则表示乐乐获得胜利。现在请你求出乐乐获胜的不同情况的总数,在对 取模后告诉他。
输入文件 parovi.in
第一行包含一个整数 。
输出文件 parovi.out
第一行输出一个整数,为乐乐获胜的不同情况的总数对 取模后的值。
2
1
乐乐只有一种取法 。
3
5
乐乐的其中一种取法为 。
4
21
提示
对于 的数据,。