天下一プログラマーコンテスト2015予選B

C - 擬二等辺三角形


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

ニシモリ君は下記の 3 つの条件を満たす三角形を“擬二等辺三角形”と呼ぶことにしました。

  • すべての辺の長さが整数である
  • すべての辺の長さが異なる
  • いずれかの二辺の長さの差が 1 となる

三角形の周長が L 以下となる擬二等辺三角形の個数を求め、1000000007 で割った余りを出力して下さい。


入力

入力は以下の形式で標準入力から与えられる。

L
  • 最大の周長 L ( 5 \leq L \leq 10^{12} ) が1行に与えられる。

出力

三角形の周長が L 以下となる擬二等辺三角形の個数を求め、 1000000007 で割った余りを出力せよ。出力の末尾に改行を入れること。

配点

この問題には部分点が設定されている。

  • L\leq 10^6 を満たすテストケース全てに正解した場合は、25 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 75 点が与えられる。

入力例1

10

出力例1

1

(a, b, c) = (2, 3, 4) のみで、それ以外 ( 例: (1,2,3)(1,2,4) ) は三角形になりません。


入力例2

1100011

出力例2

251098945

Submit提出する