广义皮萨诺周期 1

令 $F_k(n)$ 为线性递归序列，使得 $$\begin{array}{rl}{F}_k(n)& =1(1\le n\le k),\\ F_k(n)& =\sum _{i=1}^k{F}_k(n-i)(n>k).\end{array}$$

例如，$F_2(1)=1$、$F_2(2)=1$ 和 $F_2(3)=2$

令 $P(k,m)$ 为 $F_k(n)$ 模 $m$ 的（最小）周期。

给您 $P(2,10)=60$ 和 $P(2,{10}^9)=1500000000$。

找到$P(10,{10}^9)$。