一切红色都会让怪物年感到害怕。红纸也是如此……你,在 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$$。