U442561 [CUOI]函数计算
题目描述
函数$f(n)$满足
$f(x) = \begin{cases}
1 & x =1\ \\
f(x)=2f(x-1)+x & x>1 \\
\end{cases}$
求$f(k)$%$1000009$
输入格式
一行，一个数k
输出格式
见题意
说明/提示
$1\le k \le 10^{13}$