#P5003. 获胜方案

获胜方案

题目描述

乐乐和猫猫在玩一个游戏,先由乐乐在 1N1\dots N 中选出几组互质的数。例如当 N=5N=5 时,乐乐可以选择 {{1,2},{3,4},{2,5},{3,5},}\big\{\{1,2\},\{3,4\},\{2,5\},\{3,5\},\cdots\big\} 中的几组。

然后轮到猫猫。他需要找到一个 x[2,n]x\in \big[2,n\big] 使得对于乐乐选择的每组 {a,b}\{a,b\} 都满足以下两个条件之一:

  • a,b<xa, b<x

  • a,bxa, b\ge x

例如,如果乐乐选了 {{1,2},{3,4}}\big\{\{1,2\},\{3,4\}\big\},那么 xx 可以等于 33

如果猫猫找不到满足条件的 xx 值,则表示乐乐获得胜利。现在请你求出乐乐获胜的不同情况的总数,在对 10910^9 取模后告诉他。

输入文件 parovi.in

第一行包含一个整数 NN

输出文件 parovi.out

第一行输出一个整数,为乐乐获胜的不同情况的总数对 10910^9 取模后的值。

2
1

乐乐只有一种取法 {{1,2}}\big\{\{1,2\}\big\}

3
5

乐乐的其中一种取法为 {{1,2},{1,3}}\big\{\{1,2\},\{1,3\}\big\}

4
21

提示

对于 100%100\% 的数据,1N201\le N\le 20