Migrated from Lutece 2278 world domination

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

梦里什么都有。

你现在身处星空，位于$(0, 0, 0)$。$\{(x, y, z) | |x|, |y|, |z| \leq n\}$是所有行星位置的集合。一颗行星到$(0,0,0)$的线段上如果没有其他行星，就能被你看见。看见多少行星就能忘掉多少烦恼，你想要忘掉最多的烦恼。

Input

一组数据。

一行一个数n。

Output

一行一个数代表在模 1e9 + 7意义下，你能看见的行星数。

Samples

0

1

1

27

Constraints

$0\leq n \leq 10,000,000$

Note

有的东西较你想象的简单得多