0%

# 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 \pmod{1\ 000\ 000\ 007}$ and
$T(10^2,10)\equiv 782136797 \pmod{1\ 000\ 000\ 007}$.

Find $T(5000,10^{12})\mod 1\ 000\ 000\ 007$.

## 相邻约束

$(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(10,10^2)\equiv 862820094 \pmod{1\ 000\ 000\ 007}$，
$T(10^2,10)\equiv 782136797 \pmod{1\ 000\ 000\ 007}$。