C - 擬二等辺三角形
解説
/ 
/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
ニシモリ君は下記の 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