TopCoder

User's AC Ratio

85.7% (18/21)

Submission's AC Ratio

32.5% (25/77)

Description

題目資訊

最近你打算訂購N2張水樹奈奈的專輯《極限魅惑IMPACT EXCITER》。
由於份量實在是太多了,你決定分散成N份訂單。

然而,不幸的,依據博客來新的訂貨規定,每一位顧客第k次下訂單所訂的CD張數必頇是k的正整數倍。
換句話說,一位顧客第5次訂的CD張數只可能是5張、10張、15張、…依此類推。

當然,原先你把N2張CD分散在N份訂單的目的就是為了讓一張訂單中最多只會有N張CD。
即使博客來多了這項奇怪的規定,你仍然不打算捨棄你的原則,只是這樣每份訂單訂的數量可能會達不到你原來的期望。

無論如何,你還是下了訂單。為了估計你實際訂下的CD數與你期望訂下的CD數的差別,你決定把每次你少訂的數量加起來。
可是,因為你可能少訂非常多張CD,所以你希望算出少訂的總數量除以1,000,000,009的餘數。

也就是說,如果你總共要訂32張CD,分成三次訂的話,
那你第一、第二、第三次分別可以訂3、2、3張CD,分別會少訂是0+1+0=1張CD。

Input Format

輸入的第一行包含一個正整數N。

Output Format

輸出一個數字,代表最少能少訂多少張CD。

Sample Input

3

Sample Output

1

Hints

佔總分30%的測試資料中,N≦65,536。
佔總分70%的測試資料中,N≦2×109
對於所有的測試資料,N≦1×1013

Problem Source

原TIOJ1674 / 建國中學99年校內培訓contest #4 prob 2
problem setter:suhorng
source:ACM

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 3000 65536
1 3000 65536
2 3000 65536
3 3000 65536
4 3000 65536
5 3000 65536
6 3000 65536
7 3000 65536
8 3000 65536
9 3000 65536