C. xlb的数论

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

偶数 a 为集合 S 中的元素,当且仅当存在 a,(a\leq n) 个连续正整数的和为完全平方数。给定 n ,请您求出集合 S 所有元素的和。

答案可能很大,所以您需要将答案对 1000000007 取模

输入格式

输入数据中包含一行一个整数 n。

输出格式

输出一行一个整数,表示所有满足条件的整数的和。

样例

输入

8

输出

16

数据范围与提示

数据范围

60%的数据 n\leq 10^4

100%的数据 n\leq 10^{14}

样例解释

16=2+6+8

长度为2的满足条件的序列是4,5

长度为6的满足条件的序列是11,12,13,14,15,16

长度为8的满足条件的序列是1,2,3,4,5,6,7,8