显然有 $dp$，设 $f_i$ 为 $i$ 的 $lqp$ 拆分的权值和，考虑枚举拆分的最后一个数，不妨设 $f_0=1$
那么有 $f_i=sum_{j=1}^{i}f_{i-j}F_{j}$ ，$F_{i}$ 表示斐波那契数列的第 $i$ 项
变一下就是 $f_i=sum_{j=0}^{i-1}f_{j}F_{i-j}$，这样是 $n^2$ 的
然后有 $3$ 种做法，先从最容易的讲起
$1.$ 直接打表....，发现 $f_i=2f_{i-1}+f_{i-2}$
$2.$ 稍微动点脑子，$f_{i+1}-f_{i}=sum_{j=0}^{i}f_{j}F_{i+1-j}-sum_{j=0}^{i-1}f_{j}F_{i-j}$
$=sum_{j=0}^{i-1}f_{j}F_{i+1-j}+f_i-sum_{j=0}^{i-1}f_{j}F_{i-j}$
$=sum_{j=0}^{i-1}f_{j}(F_{i+1-j}-F_{i-j})+f_i$
$sum_{j=0}^{i-1}f_{j}F_{i-1-j}+f_i$
发现当 $j=i-1$ 时和式为 $0$，所以 $=sum_{j=0}^{i-2}f_{j}F_{i-1-j}+f_i$
因为 $f_{i-1}=sum_{j=0}^{i-2}f_{j}F_{i-1-j}$，所以 $f_{i+1}-f_{i}=f_{i-1}+f_{i}$
即 $f_{i+1}=2f_{i}+f_{i-1}$
上面两种方法都可以比较正常地推出式子，然后也可以矩阵优化到 $ log n$
$3.$ 考虑生成函数，设 $A(x)$ 为 $f$ 的生成函数，$G(x)$ 为 $F$ 的生成函数
那么有 $A(x)=sum_{n=0}^{infty }(f_n)x^n$，代入得到
$A(x)=sum_{n=0}^{infty}([n==0]+sum_{i=0}^{n-1}f_iF_{n-i})x^n$，感觉这个 $[n==0]$ 很烦，提出来
$A(x)=1+sum_{n=1}^{infty}(sum_{i=0}^{n-1}f_iF_{n-i})x^n$，发现 $n=0$ 时式子没贡献，$i=n$ 时式子也没贡献，所以
$A(x)=1+sum_{n=0}^{infty}(sum_{i=0}^{n}f_iF_{n-i})x^n$，这样我们就把右边变成卷积形式了
$A(x)=1+A(x)G(x)$，所以 $A(x)=frac{1}{1-G(x)}$，因为 $G(x)=frac{x}{1-x-x^2}$，代入得到
$A(x)=frac{1}{1-frac{x}{1-x-x^2}}$
$A(x)=frac{1-x-x^2}{1-2x-x^2}$
$A(x)=1+frac{x}{1-2x-x^2}$，然后经过一些(tons of)数学技巧，得到
$A(x)=1+frac{x}{(1-(1+sqrt2)x)(1-(1-sqrt2)x)}$
设 $a=1-(1+sqrt2)x,b=1-(1-sqrt2)x$，那么有 $a-b=1-1x-sqrt2x-1+1x-sqrt2x=-2sqrt2x$，则
$A(x)=1+frac{1}{2sqrt2}(frac{b-a}{ab})$
$A(x)=1+frac{1}{2sqrt2}(frac{1}{a}-frac{1}{b})$ 重新带回去得到
$A(x)=1+frac{1}{2sqrt2}(frac{1}{1-(1+sqrt2)x}-frac{1}{1-(1-sqrt2)x})$，因为 $frac{1}{1-x}=sum_{i=0}^{infty }x^i$ 所以
$A(x)=1+frac{1}{2sqrt2}(sum_{i=0}^{infty }((1+sqrt2)x)^i-sum_{i=0}^{infty }((1-sqrt2)x)^i)$
$A(x)=1+frac{1}{2sqrt2}sum_{i=0}^{infty }((1+sqrt2)^i-(1-sqrt2)^i)x^i$，倒回去得到
$f_i=frac{(1+sqrt2)^i-(1-sqrt2)^i}{2sqrt2}$
然后可以本机打表求出 $C^2 equiv 2( mod 1e9+7)$，那么 $sqrt2$ 在模 $1e9+7$ 下的逆元即为 $C$
然后直接快速幂即可
代码？这么好写就不用了吧...