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

输入数据有多组（不超过100组数据），每组数据包含一个整数N<=10¹⁸

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