问一个关于数列计算的c++解法，怎么求？

期望结果：希望能写出代码来，如果能有注释就更好了，谢谢了

Problem Description

已知an=2*an-1+n2，a0=0。输入n，计算an的值。

Input

输入数据有多组，每组数据包含一个整数n<=1018（10的18次方）。

Output

一个整数an，表示递推式第n项的值。因数字太大，结果对于1000000009取模后输出。

Sample Input

0

1

2

3

Sample Output

0

1

6

21