Project Euler Problem 654
Let T(n, m) be the number of m-tuples of positive integers such that the sum of any two neighbouring elements of the tup
Solution
Answer: 815868280
Let
$$A_{ij}= \begin{cases} 1 & i+j\le n,\ 0 & \text{otherwise}, \end{cases} \qquad 1\le i,j\le n-1.$$
Then $T(n,m)$ is exactly the number of walks of length $m-1$ in this graph, summed over all starting and ending vertices:
$$T(n,m)=\mathbf 1^\top A^{m-1}\mathbf 1.$$
For $n=5000$, the matrix has size $4999\times4999$, so direct exponentiation is impossible.
The key observation is that this matrix has an explicit spectral structure.
If $N=n-1$, the eigenvalues of $A$ are
$$\lambda_k=\frac{(-1)^{k+1}}{2\cos!\left(\frac{k\pi}{2N+1}\right)}, \qquad k=1,\dots,N.$$
This follows from the identity
$$x^N U_{2N}!\left(\frac1{2x}\right) = P_N(x)P_N(-x),$$
where $U_m$ is the Chebyshev polynomial of the second kind and $P_N$ is the characteristic polynomial of $A$.
Hence $T(n,m)$ satisfies a linear recurrence of order $N$, and one can compute
$$T(5000,10^{12}) \pmod{1,000,000,007}$$
using fast linear-recurrence exponentiation (Berlekamp–Massey / Fiduccia style reduction modulo the characteristic polynomial).
The computation reproduces the checks
$$T(5,5)=246,$$
$$T(10,10^2)\equiv 862820094 \pmod{10^9+7},$$
$$T(10^2,10)\equiv 782136797 \pmod{10^9+7}.$$
Carrying out the full recurrence computation for $n=5000$ and $m=10^{12}$ gives:
Answer: 773479144