TopCoder

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

11.5% (7/61)

Tags

Description

在遙遠的東方,有個安居樂業的小國家,稱為「櫸共和國」。
在共和國的首都,有座名聞遐邇的私立櫸學園。這座學校以高偏差值著稱,師資、設備等都相當完備。
不過,更為著名的是它的學生們。這些學生個個有著標緻的面容,並多才多藝,除了唱歌跳舞外,有些學生甚至連馬術、書法都十分擅長。
故事發生在就讀櫸學園附設小學的小葵,和就讀櫸學園的學霸 米桑身上。
         
這天,小葵正在跟米桑聊天。跟學霸聊天就有種煩惱,常常有事沒事就聊到一些冷知識。
這次,米桑又在侃侃而談的訴說她對團藻的喜愛。為了想從團藻轟炸中解脫,她展開了如下的對話

米桑:「微生物真的好可愛喔。」

小葵:「嗯。你說過了。」

米桑:「微生物看起來就好可愛好可愛。」

小葵:「哦。」

米桑:「而且牠動的樣子也好可愛喔。」

小葵:「嗯。」

米桑:「微生物分成植物類和動物類的喔。」

小葵:「哇。真的喔。 話說阿,你週末要不要跟我去逛....」

米桑:「綠色的,有葉綠體的大多是植物類的,而且大多不會動。」

小葵:「你知道嗎,鄰國的花花出了新的寫真...」

米桑:「草履蟲之類的,不是沒有顏色嗎?」

小葵:「大概吧,不過你有沒有聽說過紅白啊?他們找我們學校去表...」

米桑:「那個是動物性的,大部分都是會動的。」

小葵:「喔。原來如此。我最近在學校學到分數呢!」

歷經多番嘗試後,終於讓滔滔不絕的米桑暫停了一下。

米桑:「啊。分數啊。」

小葵:「對對對。分數!我啊,打算把世界上的所有分數全部寫出來喔!」

米桑:「可是分數有$\aleph_0$個呢!你根本列不完啦!」

小葵:「不管啦!反正我肯定列得完!」

這時米桑才想到,小學四年級的小葵只會 $1$ 到 $n$ 的數字,而且小學四年級只會教真分數,所以列完是有可能的。

米桑:「這樣的話,你要列 $ \frac {n^ 2-n} {2} $ 個數字呢,這樣你要列很久吧。」

小葵:「是喔!那我列出所有的最簡分數就好了。」

當然,聰明的米桑知道,這樣還是必須列很久,但她卻一時想不出小葵到底需要列出幾個分數。
聰明的你,幫幫她吧!告訴他到底小葵會列出多少分子分母皆小於$n$的最簡真分數。

Input Format

輸入只有一行,包含一個正整數$n$

Testdata Score Constraint
Subtask 1 0~9 10 $n\leq100$
Subtask 2 10~24 20 $n\le5000$
Subtask 3 25~44 30 $n\le 10^ 7$
Subtask 4 45~59 40 $n\le 10^{10}$

Output Format

輸出一行,包含一個非負整數,意思如題敘所示
另外,因為答案可能過大,因此請輸出答案除以$10^ 9+7$的餘數

Sample Input

6

Sample Output

11

Hints

範側中,小葵會列出
$\frac{1}{6},\ \frac{1}{5},\ \frac{1}{4},\ \frac{1}{3},\ \frac{2}{5},\ \frac{1}{2},\ \frac{3}{5},\ \frac{2}{3},\ \frac{3}{4},\ \frac{4}{5},\ \frac{5}{6}$
共 $11$個分子分母皆小於$6$的最簡真分數

Problem Source

Problem set by erd1
Description mainly from erd1, some referenced from 櫸會不會寫EP 44
米谷奈々未畢業快樂

Subtasks

For Testdata: 0 ~ 9, Score: 10
For Testdata: 10 ~ 24, Score: 20
For Testdata: 25 ~ 44, Score: 30
For Testdata: 45 ~ 59, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 524288 65536
1 1000 524288 65536
2 1000 524288 65536
3 1000 524288 65536
4 1000 524288 65536
5 1000 524288 65536
6 1000 524288 65536
7 1000 524288 65536
8 1000 524288 65536
9 1000 524288 65536
10 1000 524288 65536
11 1000 524288 65536
12 1000 524288 65536
13 1000 524288 65536
14 1000 524288 65536
15 1000 524288 65536
16 1000 524288 65536
17 1000 524288 65536
18 1000 524288 65536
19 1000 524288 65536
20 1000 524288 65536
21 1000 524288 65536
22 1000 524288 65536
23 1000 524288 65536
24 1000 524288 65536
25 1000 524288 65536
26 1000 524288 65536
27 1000 524288 65536
28 1000 524288 65536
29 1000 524288 65536
30 1000 524288 65536
31 1000 524288 65536
32 1000 524288 65536
33 1000 524288 65536
34 1000 524288 65536
35 1000 524288 65536
36 1000 524288 65536
37 1000 524288 65536
38 1000 524288 65536
39 1000 524288 65536
40 1000 524288 65536
41 1000 524288 65536
42 1000 524288 65536
43 1000 524288 65536
44 1000 524288 65536
45 1000 524288 65536
46 1000 524288 65536
47 1000 524288 65536
48 1000 524288 65536
49 1000 524288 65536
50 1000 524288 65536
51 1000 524288 65536
52 1000 524288 65536
53 1000 524288 65536
54 1000 524288 65536
55 1000 524288 65536
56 1000 524288 65536
57 1000 524288 65536
58 1000 524288 65536
59 1000 524288 65536