小明有很多长度为1的木棍,现在他打算用这些木棍摆出一些等边三角形的图案。其中每个图案都分别由边长为1的小等边三角形拼接而成,如图所示。
现在小明想知道对于一个边长为n的三角形图案,他一共能找出多少个三角形?结果对1000000007取模。
输入
输入一个数n,表示图案中大三角形的边长。
输出
输出一个数,表示图案中三角形的数量,结果对1000000007取模。
数据范围
对于100%的数据,1≤n≤10^9;
输入样例
3
输出样例
13
样例解释
对于n=3的情况,
边长为1的三角形共有9个(正向6个,倒向3个);
边长为2的三角形共有3个(正向3个)
边长为3的三角形共有1个;
共9+3+1=13个。