← 返回题目列表

Codeforces · 933/D

D. 创意剪纸

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

一切红色都会让怪物年感到害怕。红纸也是如此……你,在 Codeforces 上是红色的,无论是潜在的还是真实的。

大斑斑得到了一张有无数格点的纸,格点组成了面积相同的正方形。他最喜欢的封闭形状是圆形,因为它美丽而简单。拿到这张纸后,他就准备剪纸了。

他在上面画了n个同心圆,并将这些圆从1到n编号,使得每个圆的中心都是同一个格点,第k个圆的半径是$$\sqrt{k}$$乘以格子边的长度。

将格点的美度定义为圆的索引之和,使得该格点位于圆的内部或边界上。斑斑本想问你所有格点的美观程度总和,但又改变了主意。

定义一张有n个圆圈的纸上所有格点的总美观度为f(n),要求你算出$$(\sum_{k=1}^{m} f(k)) \bmod (10^9 + 7)$$。

输入

第一行包含一个整数 m (1 ≤ m ≤ 1012)。

输出

在第一行中打印一个表示 $$(\sum_{k=1}^{m} f(k)) \bmod (10^9 + 7)$$ 的整数。

示例

输入 #1

5

输出 #1

387

输入 #2

233

输出 #2

788243189

注意

一张有5个圆圈的纸如下所示。

共有5种格子点,其中每个红色点的美丽度为1 + 2 + 3 + 4 + 5 = 15,每个橙色点的美丽度为2 + 3 + 4 + 5 = 14,每个绿色点的美丽度为4 + 5 = 9,每个蓝色点的美丽度为5,每个灰色点的美丽度为0。因此, f(5) = 5·15 + 4·14 + 4·9 + 8·5 = 207。

类似地,f(1) = 5、f(2) = 23、f(3) = 50、f(4) = 102,因此 $$(\sum_{k=1}^{5} f(k)) \bmod (10^9 + 7) = 387$$。