---

Problem 654

---

Neighbourly Constraints

Let $T(m,n)$ be the number of $m$-tuples of positive integers such that the sum of any two neighbouring elements of the tuple is $\le n$.

For example, $T(3,4)=8$, via the following eight $4$-tuples:
$(1,1,1,1)$
$(1,1,1,2)$
$(1,1,2,1)$
$(1,2,1,1)$
$(1,2,1,2)$
$(2,1,1,1)$
$(2,1,1,2)$
$(2,1,2,1)$

You are also given that $T(5,5)=246$,
$T(10,{10}^2)\equiv 862820094(\mathrm{mod}1000000007)$ and
$T({10}^2,10)\equiv 782136797(\mathrm{mod}1000000007)$.

Find $T(5000,{10}^{12})\mathrm{mod}1000000007$.

---

相邻约束

记$T(m,n)$为任意相邻元素之和$\le n$的所有$m$-元正整数组的数目。

例如，$T(3,4)=8$这八个$4$元组分别是：
$(1,1,1,1)$
$(1,1,1,2)$
$(1,1,2,1)$
$(1,2,1,1)$
$(1,2,1,2)$
$(2,1,1,1)$
$(2,1,1,2)$
$(2,1,2,1)$

已知$T(5,5)=246$，
$T(10,{10}^2)\equiv 862820094(\mathrm{mod}1000000007)$，
$T({10}^2,10)\equiv 782136797(\mathrm{mod}1000000007)$。

求$T(5000,{10}^{12})\mathrm{mod}1000000007$。

---