0697 - 素数のWA

---

この前のアレです。(どれ)

---

問題

整数nに対し、n以下の素数の和を10⁹+9で割った余りを出力せよ。

入力

n

整数nが与えられる。

出力

n以下の素数の和を10⁹+9で割った余りを出力せよ。
出力の最後に改行を入れること。

制約

• 小課題1: 0 ≦ n ≦ 10⁴
• 小課題2: 0 ≦ n ≦ 10⁶
• 小課題3: 0 ≦ n ≦ 10⁷*5

(オーダーがとても怪しいので何かあったら連絡ください)
(予告なしにリジャッジされる可能性があります)
2017/04/28_18:37_rejudged

---

入出力例

入力例1

4

出力例1

5

入力例2

10

出力例2

17