題目資訊

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

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

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

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

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