← 返回题目列表

AtCoder · tenka1_2015_qualB_c

C. 伪等腰三角形

中文机器翻译题面 查看原题

問題文

NISHIMORI 君将下面的 3 条件满足的三角形称为“拟等腰三角形”。

  • 所有边的长度都是整数。
  • 所有边的长度都不同
  • 任意两边长度的差为 1 变为

三角形的周长为 L 求周长以下的拟等腰三角形的个数,1000000007 后的余数。


入力

输入是按以下格式从标准输入给出的。

L
  • 最大的周长 L ( 5 \leq L \leq 10^{12} ) 在一行中给出。

出力

三角形的周长为 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