問題文
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