### 问题描述 令 $f\left ( n \right ) =2\times f\left ( n-1 \right ) +3\times f\left ( n-2 \right ) +n,f\left ( 1 \right ) =1,f\left ( 2 \right ) =2$。 告诉你 $n$，输出 $f\left ( n \right )$ 的结果，结果对 $1e9+7$ 取模。 ### 输入格式 多组输入，每行一个整数 $n（1\le n \le 1000)$，如果输入为 $0$，停止程序。 ### 输出格式f 输出对应 $f\left ( n \right ) $ 的值，结果对 $1e9+7$ 取模 ### 样例输入 ```text 1 5 9 456 0 ``` ### 样例输出 ```text 1 95 7789 734891569 ```