0697 - 素数のWA

時間制限 1 秒 / メモリ制限 256 MB / 得点 3 / Writer fal_rnd / x 16 / 統計 /


TLE
1sec
MLE
256MB
得点
3

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

問題

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

入力

n

整数nが与えられる。

出力

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

制約

  • 小課題1: 0 ≦ n ≦ 104
  • 小課題2: 0 ≦ n ≦ 106
  • 小課題3: 0 ≦ n ≦ 107*5
(オーダーがとても怪しいので何かあったら連絡ください)
(予告なしにリジャッジされる可能性があります)
2017/04/28_18:37_rejudged

入出力例

入力例1

4

出力例1

5

入力例2

10

出力例2

17