Luogu4451 [国家集训队] 整数的lqp拆分

题意：给定常数 。对不定长有序序列 ，若满足 ，则称该序列合法。

对于所有合法数列，求 之和，其中 是斐波那契数列。

答案对 取模，，时限 。

---

根据组合意义，可以看做有 种长度为 的骨牌，要拼成一个长度为 的有序序列的方案数。

其中 枚举了长度的划分， 是向划分中填写骨牌的方案数。

根据 SEQ 变换，答案的生成函数 根据多项式求逆的递推算法， 的系数是线性递推（容易写出递推式），可以矩阵快速幂求解。

复杂度 。