每一天都是假期重温

在 J 行星上，一年持续 $D$ 天。假期由以下两条规则定义。
1。现任天皇登基之初，自当年起将他的生日定为假日。
2。如果$d$的前一天和后一天都是假期，那么$d$也成为假期。

最初没有假期。令 $f(n,d)$ 为方法数，使得一年中的所有天数正好在 $d$ 天之后为假期，一年持续 $n$ 天。

您获得了 $f(4,2)=4$、$f(10,5)=240$、$f(50,100)mod1000000007=263154905$。

找到 $f(1000,{10}^{12})mod1000000007$。

---

感谢 百黑客 为了这个想法。

这个问题的灵感来自 Project Euler 的 Problem 645 (https://projecteuler.net/problem=645)