暂无测试数据。

又哭又笑的

今天的你还真是难懂

明天天气又会怎么样呢

现在的你真是难以预测

——五郎

五郎陷于困境之中，莓为了解救他，需要知道他们携带的三角炸弹的威力

给出三角炸弹的边长之和，三角炸弹的威力为周长和三角炸弹周长相等的三角形的个数

注意边是无序的，即 $3,4,5$ 和 $4,5,3$ 算同一个三角形.

答案对 $10^9+7$ 取模.

输入格式

一行一个整数 $n$

输出格式

一行一个整数表示三角炸弹的威力.

数据范围

对于 $40\%$ 的数据，$n\leq 10^7$

对于 $60\%$ 的数据，$n\leq 10^9$

对于 $100\%$ 的数据，$1\leq n\leq 10^{18}$

10

2

100000000

331875002