TopCoder

Thumb 1580873255888  1
Kevin_Zhang
\(I\ want\ to\ be\ better!\ But\ how.....\)

User's AC Ratio

75.0% (30/40)

Submission's AC Ratio

19.3% (38/197)

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

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10