### 问题描述 令 $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$。 令 $g(n)=g(n-1)+f(n)+n\times n,g(1)=2$。 告诉你 $n$，输出 $g\left ( n \right )$ 的结果，结果对 $1e9+7$ 取模。 ### 输入格式 多组输入，每行一个整数 $n(1\le n \le 10^{9})$，如果输入为 $0$，停止程序。 ### 输出格式 输出对应 $g \left ( n \right ) $ 的值，结果对 $1e9+7$ 取模 ### 样例输入 ```text 1 5 9 456 0 ``` ### 样例输出 ```text 1 95 7789 734891569 ``` ### 说明 多组输入，输入为 $0$ 时，终止程序。