Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem E: 递推

Problem E: 递推

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 148  Solved: 19
[Submit][Status][Web Board]

Description

JYMXJ转眼就从小学上了高中。在学习递推的时候,JYM在纸上随手写了一个递推关系式:an=2*an-1a0=0。写完这个递推式,JYM拿给XJ看,XJ觉得太过简单,于是大笔一挥,在等式右边又加了一个式子,变成了这样:an=2*an-1+n2JYM看到这个式子,想要算几个项来看看,可是一算就发现这个数据量太大了,你能帮他解决这个问题吗?

Input

输入数据有多组(不超过100组数据),每组数据包含一个整数N<=1018

Output

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

Sample Input

0
1
2
3

Sample Output

0
1
6
21

HINT

[Submit][Status][Web Board]